Towards Constructing Destination Node Index for Repetition Paths

概要

Graph database management systems (GDBMSs) enable users to traverse one edge at a fixed computing cost for vast and complex graph data. However, GDBMSs cannot avoid reaching already-scanned nodes from different starting nodes by repeatedly traversing edges, which we name a repetition path, with a specific relationship type. Therefore, when a GDBMS reaches a high degree node (HDN), the number of graph traversals increases in proportion to the number of its adjacent nodes. Consequently, the cost of traversing repetition paths extremely increases affected by HDNs in conventional GDBMSs. In this paper, we propose a graph index structure to repeatedly traverse edges belonging to a specific relationship type by distinguishing between HDNs and other nodes. Moreover, we also propose a method for compressing our index to take advantage of the characteristics of real-world networks so that a graph index tends to be the easily huge size of index files.

引用情報

Kazuma Kusu, Takahiro Komamizu, Kenji Hatano, Towards Constructing Destination Node Index for Repetition Paths, IPSJ SIG Technical Report, Vol.2022-DBS-175, No.15, 2022-09-09.