RPQBench: A Benchmark for Regular Path Queries on Graph Data

RPQBench: A Benchmark for Regular Path Queries on Graph Data

연구 분야: Databases

학회: International Conference on Web Information Systems Engineering

The development of knowledge graphs represents a significant milestone in the field of symbolism, offering a suitable data model for describing intricate resource relationships across diverse domains. Regular Path Queries (RPQs) have gained considerable attention in the field of knowledge graphs as they serve as the predominant form of navigational queries. Their widespread research and discussion in recent years have made them a research focus of investigation. Due to the lack of a dedicated benchmark for RPQs, in this paper, we have developed RPQBench, the first benchmark specifically designed for evaluating RPQ algorithms. The RPQBench can effectively generate graph data consisting of a specified amount of paths whose lengths conform to the power-law distribution. Additionally, based on statistical results from real corpora and a review of existing research on RPQs, we propose a set of benchmark queries, which include all typical regular expression operators and cover all typical patterns of RPQs that match paths of various lengths. We have benchmarked the state-of-the-art graph database systems with RPQ feature using RPQBench. The experimental results show that our RPQBench is effective and efficient in evaluating RPQ performance of graph databases.