Recurrent Path Index for Efficient Graph Traversal

概要

Graph databases (GDB) enable us to conduct a query for searching and analyzing graph data efficiently. However, such a query has to extract sub-graphs in the beginning, so this process is high cost due to the NP-complete problem. GDBs find out sub-graphs specified in a query by graph traversal that is a process following edges from a node. Moreover, it enables them to traverse an edge at a constant cost, but graph traversal involving some edges is affected by database volume due to the increase of candidate that it has to traverse edges. To improve the performance of graph traversal more efficiently, it is necessary to reduce the number of times for graph traversal on conducting a query. In this study, we focus on traversing some edges having the same relationship recurrently. Therefore, we propose a new graph index for enabling to traverse the same type edges efficiently to improve the performance of sub-graph searching.

引用情報

Kazuma Kusu, Kenji Hatano, Recurrent Path Index for Efficient Graph Traversal, Proceedings of 2019 IEEE International Conference on Big Data (Big Data), pp.6107-6109, 2019-12-09, DOI: 10.1109/BigData47090.2019.9006295.