An Algorithm for All-Pairs Regular Path Problem on External Memory Graphs

Nobutaka SUZUKI  Kosetsu IKEDA  Yeondae KWON  

IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.4   pp.944-958
Publication Date: 2016/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015DAP0018
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)
graph data,  regular path query,  

Full Text: PDF(1.8MB)>>
Buy this Article

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.