Robust Recursive Query Parallelism in Graph Database Management Systems

Summary: Defines a morsel-dispatching design space unifying source-, frontier-, and multi-source BFS parallelisms for recursive graph queries. Implements a hybrid source+frontier morsel policy with multi-source packing in Kuzu, empirically achieving robust multi-core scaling and scan reduction when many sources exist. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h1e0808362b8e86a5
Venue: VLDB
Year: 2025
Pagerank: 5.3942942e-05
Overall Rank: 8,071 | 45.74%
DOI: 10.14778/3749646.3749706

Incoming Non-self Citations Over Time

Authors

1. Anurag Chakraborty (University of Waterloo)
2. Semih Salihoğlu (University of Waterloo)

BibTeX Citation

@article{chakraborty_vldb25,
        title = {{Robust Recursive Query Parallelism in Graph Database Management Systems}},
        author = {Chakraborty, Anurag and Salihoğlu, Semih},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {11},
        pages = {4465--4477},
        doi = {10.14778/3749646.3749706},
        url = {https://doi.org/10.14778/3749646.3749706},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,867	Nav-Index: A High-Performance, Adaptive Index for Shortest Path Queries in RDBMS	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012092602
22	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00055962491
71	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00037720227
93	Encapsulation of Parallelism in the Volcano Query Processing System	1990	SIGMOD	0.00034622929
215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00024598661
373	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00019711632
1,081	Hybrid Parallelization Strategies for Large-Scale Machine Learning in SystemML	2014	VLDB	0.00012123917
1,442	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010639351
1,752	Kuzu* Graph Database Management System	2023	CIDR	9.7289339e-05
3,055	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	7.6979859e-05
10,330	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB	5.0312167e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	6,608	Revisiting Pipelined Parallelism in Multi-Join Query Processing	2005	VLDB
3	2,305	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
4	9,621	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB
5	3,775	Parallelizing Query Optimization	2008	VLDB
6	5,692	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB
7	215	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD
8	12,048	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR
9	4,888	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
10	1,752	Kuzu* Graph Database Management System	2023	CIDR