Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows

Summary: Distributed, worst-case-optimal evaluation of fixed-size subgraphs via data-parallel, low-memory dataflows on dynamic graphs. Memory is linear in input edges; per-worker work, communication, and memory scale linearly with the number of workers, robust to adversarial skew; generalizes to dynamic equi-joins. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11776
Venue: VLDB
Year: 2018
Pagerank: 9.9665955e-05
Overall Rank: 1,953 | 86.42%
DOI: 10.14778/3184470.3184473

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,561	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.00011358946
1,924	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010077055
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
3,036	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6735171e-05
3,287	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	7.2739447e-05
3,641	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	6.8884895e-05
3,778	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7747398e-05
4,236	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.3335374e-05
4,556	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0883757e-05
4,968	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	5.7956205e-05
5,009	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	5.761237e-05
5,570	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	5.4284968e-05
5,728	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.3507988e-05
5,773	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3319911e-05
5,811	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	5.317401e-05
6,081	Subgraph Matching over Graph Federation	2022	VLDB	5.2208051e-05
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
6,395	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0829204e-05
6,441	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0603113e-05
7,126	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8232367e-05
7,675	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.6817479e-05
7,934	Fast Local Subgraph Counting	2024	VLDB	4.613363e-05
8,795	Graphsurge: Graph Analytics on View Collections Using Differential Computation	2021	SIGMOD	4.4499973e-05
9,267	PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware	2024	SIGMOD	4.3663649e-05
9,330	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.3556432e-05
9,366	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3493859e-05
9,518	Banyan: A Scoped Dataflow Engine for Graph Query Service	2022	VLDB	4.3328897e-05
9,727	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2942813e-05
9,788	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2818172e-05
9,940	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	4.2456408e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1945683e-05
10,199	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD	4.1945683e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1945683e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1945683e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1945683e-05
10,292	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	4.1945683e-05
10,514	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 24 of 24 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923
55	Efficiently Updating Materialized Views	1986	SIGMOD	0.00065762967
95	Maintaining Views Incrementally	1993	SIGMOD	0.00050896659
288	Storm @Twitter	2014	SIGMOD	0.00028939871
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
461	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022499343
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
586	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019685374
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
919	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015343179
1,308	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012661651
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
1,500	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011674394
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493
1,675	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010947606
1,756	Graphflow: An Active Graph Database	2017	SIGMOD	0.00010664542
2,196	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.3089621e-05
2,212	Skew in Parallel Query Processing	2014	PODS	9.2771827e-05
2,228	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.2385241e-05
2,801	Scalable Distributed Subgraph Enumeration	2017	VLDB	8.0992955e-05
3,833	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7173578e-05
8,253	SPARTex: A Vertex-Centric Framework for RDF Data Analytics	2015	VLDB	4.5493149e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,129	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.5008242e-05
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
5,949	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2595857e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1945683e-05
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
5,054	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	5.7321997e-05
1,877	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010236803
3,232	Managing Large Dynamic Graphs Efficiently	2012	SIGMOD	7.336861e-05
7,153	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8153963e-05
4,556	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0883757e-05