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: 11777
Venue: VLDB
Year: 2018
Pagerank: 9.9938634e-05
Overall Rank: 1,948 | 86.47%
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,334	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012543633
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
1,906	In-Memory Subgraph Matching: An In-depth Study	2020	SIGMOD	0.00010135267
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05
3,034	RapidMatch: A Holistic Approach to Subgraph Query Processing	2021	VLDB	7.6737281e-05
3,287	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	7.2689944e-05
3,488	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	7.0460627e-05
3,781	A Learned Sketch for Subgraph Counting	2021	SIGMOD	6.7691344e-05
4,238	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.3274465e-05
4,554	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0839934e-05
4,756	Efficient GPU-Accelerated Subgraph Matching	2023	SIGMOD	5.9364786e-05
5,002	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	5.7610359e-05
5,502	Circinus: Fast Redundancy-Reduced Subgraph Matching	2023	SIGMOD	5.4730826e-05
5,573	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	5.4268881e-05
5,782	I/O-Efficient Butterfly Counting at Scale	2023	SIGMOD	5.3268721e-05
5,809	Fast and Robust Distributed Subgraph Enumeration	2019	VLDB	5.3175972e-05
5,968	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.2469955e-05
6,086	Subgraph Matching over Graph Federation	2022	VLDB	5.2157921e-05
6,391	An In-Depth Study of Continuous Subgraph Matching	2022	VLDB	5.0780425e-05
6,436	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.0554554e-05
7,122	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	4.8199209e-05
7,674	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.677258e-05
7,936	Fast Local Subgraph Counting	2024	VLDB	4.6089395e-05
8,792	Graphsurge: Graph Analytics on View Collections Using Differential Computation	2021	SIGMOD	4.4457318e-05
9,272	PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware	2024	SIGMOD	4.3621803e-05
9,335	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	4.351469e-05
9,375	In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework	2024	SIGMOD	4.3452177e-05
9,519	Banyan: A Scoped Dataflow Engine for Graph Query Service	2022	VLDB	4.3287375e-05
9,726	MatCo: Computing Match Cover of Subgraph Query over Graph Data	2025	SIGMOD	4.2901665e-05
9,791	A Modular Graph-Native Query Optimization Framework	2025	SIGMOD	4.2777144e-05
9,940	Worst-Case-Optimal Similarity Joins on Graph Databases	2024	SIGMOD	4.241573e-05
10,131	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD	4.1905499e-05
10,199	R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization	2026	SIGMOD	4.1905499e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1905499e-05
10,264	CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination	2026	VLDB	4.1905499e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1905499e-05
10,304	Aquila: A High-Concurrency System for Incremental Graph Query	2026	VLDB	4.1905499e-05
10,523	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1905499e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1905499e-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.0019040811
55	Efficiently Updating Materialized Views	1986	SIGMOD	0.00065687017
97	Maintaining Views Incrementally	1993	SIGMOD	0.00050863077
287	Storm @Twitter	2014	SIGMOD	0.00028917909
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
460	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022679846
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
585	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019682634
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
916	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00015326675
1,312	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012650678
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
1,487	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011691164
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
1,676	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.000109374
1,746	Graphflow: An Active Graph Database	2017	SIGMOD	0.0001069135
2,178	Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs	2014	VLDB	9.3645765e-05
2,199	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.3082437e-05
2,216	Skew in Parallel Query Processing	2014	PODS	9.2693784e-05
2,787	Scalable Distributed Subgraph Enumeration	2017	VLDB	8.1219297e-05
3,831	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	6.7146681e-05
8,249	SPARTex: A Vertex-Centric Framework for RDF Data Analytics	2015	VLDB	4.5449877e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1905499e-05
5,951	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2547916e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
5,051	Performance Guarantees for Distributed Reachability Queries	2012	VLDB	5.7267112e-05
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
3,234	Managing Large Dynamic Graphs Efficiently	2012	SIGMOD	7.3302974e-05
7,154	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8107765e-05
4,554	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0839934e-05