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

References(22)*help

See more

Details 詳細情報について

Report a problem

Back to top