DBScholar

Back to papers

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

Summary: Distributed worst-case-optimal dataflows for dynamic subgraph queries and equi-joins, with linear total memory and provably linear per-worker scaling despite adversarial skew. Implemented in Timely Dataflow and evaluated on graphs up to 64B edges. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
h51f7fbf959dadb20
Venue
VLDB
Year
2018
Pagerank
0.00011334813
Overall Rank
1,252 | 91.59%
DOI
10.14778/3184470.3184473

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{ammar_vldb18,
        title = {{Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows}},
        author = {Ammar, Khaled and McSherry, Frank and Salihoglu, Semih and Joglekar, Manas},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {6},
        pages = {691--704},
        doi = {10.14778/3184470.3184473},
        url = {https://doi.org/10.14778/3184470.3184473},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 40 of 40 citing papers.

Rank Citing Paper Year Venue Pagerank
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021236408
713 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014571507
961 Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together 2019 SIGMOD 0.00012830477
1,180 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011622165
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
2,017 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1788573e-05
2,468 GPU-Accelerated Subgraph Enumeration on Partitioned Graphs 2020 SIGMOD 8.4138334e-05
2,775 GraphScope: A Unified Engine For Big Graph Processing 2021 VLDB 8.0288982e-05
3,012 Efficient GPU-Accelerated Subgraph Matching 2023 SIGMOD 7.7512751e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,848 Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs 2021 SIGMOD 6.9798476e-05
3,881 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9477894e-05
4,077 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8156109e-05
4,124 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7895411e-05
4,512 Circinus: Fast Redundancy-Reduced Subgraph Matching 2023 SIGMOD 6.5650165e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
5,402 Fast and Robust Distributed Subgraph Enumeration 2019 VLDB 6.1465532e-05
5,560 I/O-Efficient Butterfly Counting at Scale 2023 SIGMOD 6.0822136e-05
5,673 Subgraph Matching over Graph Federation 2022 VLDB 6.0404425e-05
5,684 iTurboGraph: Scaling and Automating Incremental Graph Analytics 2021 SIGMOD 6.0362827e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.9234316e-05
6,235 Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding 2024 VLDB 5.8403639e-05
6,896 PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware 2024 SIGMOD 5.6513703e-05
7,250 Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale 2022 VLDB 5.5720266e-05
7,535 Fast Local Subgraph Counting 2024 VLDB 5.4983904e-05
8,991 Graphsurge: Graph Analytics on View Collections Using Differential Computation 2021 SIGMOD 5.2412183e-05
9,038 MatCo: Computing Match Cover of Subgraph Query over Graph Data 2025 SIGMOD 5.2315688e-05
9,157 In-depth Analysis of Continuous Subgraph Matching in a Common Delta Query Compilation Framework 2024 SIGMOD 5.216524e-05
9,666 Parallel Query Processing: To Separate Communication from Computation 2022 SIGMOD 5.142891e-05
9,720 Banyan: A Scoped Dataflow Engine for Graph Query Service 2022 VLDB 5.1334824e-05
10,131 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0727027e-05
10,260 A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis] 2026 SIGMOD 5.0480912e-05
10,308 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.0377711e-05
10,686 R2O: A Dual-Layer Framework for Joint Rewriting and Ordering in Distributed Property Graph Query Optimization 2026 SIGMOD 4.9769913e-05
10,718 A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs 2026 VLDB 4.9769913e-05
10,744 CEMR: An Effective Subgraph Matching Algorithm with Redundant Extension Elimination 2026 VLDB 4.9769913e-05
10,750 Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration 2026 VLDB 4.9769913e-05
10,998 Aquila: A High-Concurrency System for Incremental Graph Query 2026 VLDB 4.9769913e-05
11,212 cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns 2025 SIGMOD 4.9769913e-05
11,552 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 4.9769913e-05
Previous Page 1 / 1 Next

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
3 Pregel: A System for Large-Scale Graph Processing 2010 SIGMOD 0.0012087459
39 Efficiently Updating Materialized Views 1986 SIGMOD 0.00046583225
62 Maintaining Views Incrementally 1993 SIGMOD 0.00039040346
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024899872
231 Storm @Twitter 2014 SIGMOD 0.00023830094
289 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00021960834
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
402 Worst-case Optimal Join Algorithms 2012 PODS 0.00019095982
408 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00018894165
443 Efficient Subgraph Matching on Billion Node Graphs 2012 VLDB 0.00018190518
489 TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases 2013 SIGMOD 0.00017440023
784 Distance-Join: Pattern Match Query In a Large Graph Database 2009 VLDB 0.00014015324
1,042 Parallel Subgraph Listing in a Large-Scale Graph 2014 SIGMOD 0.00012331317
1,046 Graphflow: An Active Graph Database 2017 SIGMOD 0.00012316579
1,233 Communication Steps for Parallel Query Processing 2013 PODS 0.00011404978
1,410 A Distributed Graph Engine for Web Scale RDF Data 2013 VLDB 0.00010737126
1,482 Skew in Parallel Query Processing 2014 PODS 0.00010534147
1,546 Upper and Lower Bounds on the Cost of a Map-Reduce Computation 2013 VLDB 0.0001029751
1,726 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7857214e-05
1,804 gStore: Answering SPARQL Queries via Subgraph Matching 2011 VLDB 9.5980088e-05
1,876 Real-Time Twitter Recommendation: Online Motif Detection in Large Dynamic Graphs 2014 VLDB 9.4535107e-05
2,022 Scalable Distributed Subgraph Enumeration 2017 VLDB 9.1686153e-05
2,464 Output-optimal Parallel Algorithms for Similarity Joins 2017 PODS 8.4221003e-05
7,162 SPARTex: A Vertex-Centric Framework for RDF Data Analytics 2015 VLDB 5.5938323e-05
Previous Page 1 / 1 Next

Semantically Similar Papers