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: 14247
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,982 | 24.66%
DOI: 10.14778/3749646.3749706

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

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 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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.0012250108
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
98	Encapsulation of Parallelism in the Volcano Query Processing System	1990	SIGMOD	0.00034510605
103	DuckDB: an Embeddable Analytical Database	2019	SIGMOD	0.00034161428
241	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD	0.00023654664
422	Umbra: A Disk-Based System with In-Memory Performance	2020	CIDR	0.00018732744
1,079	Hybrid Parallelization Strategies for Large-Scale Machine Learning in SystemML	2014	VLDB	0.00012258469
1,432	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.0001080346
2,126	Kuzu* Graph Database Management System	2023	CIDR	9.1329991e-05
3,018	The LDBC Social Network Benchmark: Business Intelligence Workload	2023	VLDB	7.8473755e-05
10,103	Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs	2022	VLDB	5.1466947e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	6,515	Revisiting Pipelined Parallelism in Multi-Join Query Processing	2005	VLDB
3	2,337	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
4	9,446	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB
5	3,726	Parallelizing Query Optimization	2008	VLDB
6	5,563	A Parallel Processing Strategy for Evaluating Recursive Queries	1986	VLDB
7	241	Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age	2014	SIGMOD
8	11,745	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR
9	4,773	Parallel Processing of Recursive Queries in Distributed Architectures	1989	VLDB
10	2,126	Kuzu* Graph Database Management System	2023	CIDR