An External Memory Algorithm for All-Pairs Regular Path Problem

Autor:	Kosetsu Ikeda, Yeondae Kwon, Nobutaka Suzuki
Rok vydání:	2015
Předmět:	Matching (graph theory) Computer science Path (graph theory) Node (circuits) Algorithm Auxiliary memory Longest path problem Graph
Zdroj:	Lecture Notes in Computer Science ISBN: 9783319228518 DEXA (2)
DOI:	10.1007/978-3-319-22852-5_34
Popis:	In this paper, we consider solving the all-pairs regular path problem on large graphs efficiently. Let G be a graph and r be a regular path query, and consider finding the answers of r on G. If G is so small that it fits in main memory, it suffices to load entire G into main memory and traverse G to find paths matching r. However, if G is too large and cannot fit in main memory, we need another approach. In this paper, we propose an external memory algorithm for solving all-pairs regular path problem on large graphs. Our algorithm finds the answers matching r by scanning the node list of G sequentially, which avoids random accesses to disk and thus makes regular path query processing I/O efficient.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::578ea49ed52946c0eefb0f764af879eb https://doi.org/10.1007/978-3-319-22852-5_34 Zobrazit plný text záznamu