Repetition path destination index for repeated graph traversal using adjacency lists

Graph Database Management Systems (GDBMSs) suffer from costly "repetition paths" caused by repeatedly traversing edges through high-degree nodes (HDNs). We propose a novel graph index that distinguishes HDNs to optimize these specific traversals. To build this potentially large index efficiently, we also introduce a recursive scan operation. Our experiments show significant results. The index improved repeated traversal performance by up to 1,176 times in a large graph. Moreover, the recursive scan operation reduced indexing time by up to 64.6% compared to a naive construction method. This demonstrates a powerful, two-part solution for a critical GDBMS bottleneck.