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

DOI 機関リポジトリ 機関リポジトリ (HANDLE) Web Site 参考文献22件 オープンアクセス
  • 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

この論文をさがす

説明

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.

収録刊行物

参考文献 (22)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ