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

Access this Article

Search this Article

Author(s)

    • 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

Abstract

In this paper, we consider solving the all-pairs regular path problem on large graphs efficiently. Let <i>G</i> be a graph and <i>r</i> be a regular path query, and consider finding the answers of <i>r</i> on <i>G</i>. If <i>G</i> is so small that it fits in main memory, it suffices to load entire <i>G</i> into main memory and traverse <i>G</i> to find paths matching <i>r</i>. However, if <i>G</i> 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 <i>r</i> by scanning the node list of <i>G</i> 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

Codes

Page Top