LSQB: A Large-Scale Subgraph Query Benchmark

Amine Mhedhbi, Matteo Lissandrini, Laurens Kuiper, Jack Waudby, Gabor Szarnyas

Download a digital copy (PDF) or get the code

The final authenticated version is available online at 10.1145/3461837.3464516.

This work has been presented Sun. June 20th, online

Abstract:

We introduce LSQB, a new large-scale subgraph query benchmark. LSQB tests the performance of database management systems on an important class of subgraph queries overlooked by existing benchmarks. Matching a labelled structural graph pattern, referred to as subgraph matching, is the focus of LSQB. In relational terms, the benchmark tests DBMSs join performance as a choke-point since subgraph matching is equivalent to multi-way joins between base Vertex and base Edge tables on ID attributes. The benchmark focuses on read-heavy workloads by relying on global queries which have been ignored by prior benchmarks. Global queries, also referred to as unseeded queries, are a type of queries that are only constrained by labels on the query vertices and edges. LSQB contains a total of nine queries and leverages the LDBC social network data generator for scalability. The benchmark gained both academic and industrial interest and is used internally by 5+ different vendors.

Cite:

and
“LSQB: A Large-Scale Subgraph Query Benchmark.” Proceedings of the 4th Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA). Co-located with SIGMOD 2021 

@inproceedings{10.1145/3461837.3464516,
author = {Mhedhbi, Amine and Lissandrini, Matteo and Kuiper, Laurens and Waudby, Jack and Sz\'{a}rnyas, G\'{a}bor},
title = {LSQB: A Large-Scale Subgraph Query Benchmark},
year = {2021},
isbn = {9781450384773},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3461837.3464516},
doi = {10.1145/3461837.3464516},
booktitle = {Proceedings of the 4th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA)},
articleno = {8},
numpages = {11},
location = {Virtual Event, China},
series = {GRADES-NDA '21}
}