2024/12/13 by Georgiy Belyanin, Belyanin, Georgiy, Semyon Grigoriev +2
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2412.10287
openalex publication_date 2024/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Two-way regular path queries (2-RPQs) allow one to use regular languages over edges and inverted edges in edge-labelled graph to constrain paths of interest. 2-RPQs are (partially) adopted in different real-world graph analysis systems and have become a part of the GQL ISO standard. However the performance of 2-RPQs on real-world graphs remains a bottleneck for wider adoption. Utilisation of high-performance sparse linear algebra libraries for the algorithm implementation allows one to achieve significant speedup over competitors on real-world data and queries. We propose a new breadth-first-search-based algorithm that leverages linear algebra for evaluating single-source regular path queries. We integrate it into the LAGraph graph processing algorithm infrastructure and provide in-depth performance comparison on the large real-world knowledge bases. Additionally, we present extensive analysis of its performance across different query types using synthetic data, comparing it with various databases and other linear algebra-based approaches.