Linear Algebra-based Regular Path Queries

This is a repository with utils that can be used to reproduce experiments described in Single-Source Regular Path Querying in Terms of Linear Algebra paper. The paper is about evaluating graph Regular Path Queries using linear algebra over sparse adjacency matrices implemented using SuiteSparse:GraphBLAS.

Datasets

Currently, we use the following datasets for the experiments information on which is available within the Datasets directory.

• Wikidata snapshot from MillenniumDB path-query-challenge this is a snapshot of a real-world Wikidata graph and 660 queries taken from the query log.
• Yago-2S knowledge base is a large knowledge base evaluated with 7 complex RPQ queries taken from academic papers.

Reproducing experiments

For running the experiments in a specific environment refer to Databases folder with information on evaluating the experiments. These are the competitors.

• rpq-matrix is another linear algebra-based algorithm for evaluating RPQs using their own implementation of sparse matrices.
• MillenniumDB is a graph database demonstrating state-of-the-art performance among other competitors and that might cache the data to execute queries out of the RAM.
• FalkorDB (ex. RedisGraph) is an in-memory graph database employing SuiteSparse:GraphBLAS sparse matrix approaches for query evaluation.
• Memgraph is quite advanced in-memory graph database.

Authors

• Semyon Grigorev (mail: [email protected]).
• Georgiy Belyanin (mail: [email protected]).
• Rodion Suvorov (mail: [email protected]).

Acknowledgments & copyright notices

LA-RPQ is licensed under GPL-2.0 license and acknowledges the following projects and modifications made to them.

• MillenniumDB licensed under GPL-2.0 used in two different versions with modifications to the RDF prefix handling. For more information see the ./Databases/MillenniumDB directory.
• rpq-matrix licensed under GPL-3.0 used both w/o modifications and with modifications to work with GraphBLAS.
• Blazegraph licensed under GPL-2.0 used without modifications but with custom benchmarking scripts that uses procedures from the unlicensed MillenniumDB WDBench but configured for different datasets and only for the Blazegraph database.

We also appreciate Vladimir Kutuev(mail: [email protected]) for consulting us on the proper engineering approaches to use.

Thank you for you interest in the la-rpq project.