An Algorithm for All-Pairs Regular Path Problem on External Memory Graphs
-
- SUZUKI Nobutaka
- Faculty of Library, Information and Media Science, University of Tsukuba
-
- IKEDA Kosetsu
- Graduate School of Library, Information and Media Studies, University of Tsukuba
-
- KWON Yeondae
- Graduate School of Agricultural and Life Sciences, The University of Tokyo
Search this article
Description
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 a novel approach based on external memory algorithm. Our algorithm finds the answers matching r by scanning the node list of G sequentially. We made a small experiment, which suggests that our algorithm can solve the problem efficiently.
Journal
-
- IEICE Transactions on Information and Systems
-
IEICE Transactions on Information and Systems E99.D (4), 944-958, 2016
The Institute of Electronics, Information and Communication Engineers
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390282679354265344
-
- NII Article ID
- 130005141354
-
- NII Book ID
- AA10826272
-
- ISSN
- 17451361
- 09168532
-
- HANDLE
- 2241/00143072
-
- Text Lang
- en
-
- Data Source
-
- JaLC
- IRDB
- Crossref
- CiNii Articles
-
- Abstract License Flag
- Disallowed