Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs
Summary: Mitigates memory blowup in differential maintenance for recursive graph queries by dropping operator differences and recomputing. Uses deterministic and probabilistic structures to track dropped diffs, enabling scalable DC-based query maintenance. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Khaled Ammar (BorealisAI; University of Waterloo)
- 2. Siddhartha Sahu (University of Waterloo)
- 3. Semih Salihoglu (University of Waterloo)
- 4. M. Tamer Özsu (University of Waterloo)
BibTeX Citation
@article{ammar_vldb22,
title = {{Optimizing Differentially-Maintained Recursive Queries on Dynamic Graphs}},
author = {Ammar, Khaled and Sahu, Siddhartha and Salihoglu, Semih and Özsu, M. Tamer},
journal = {PVLDB},
series = {{VLDB} '22},
volume = {15},
number = {11},
pages = {3186--3198},
doi = {10.14778/3551793.3551862},
url = {https://doi.org/10.14778/3551793.3551862},
year = {2022}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,071 | Robust Recursive Query Parallelism in Graph Database Management Systems | 2025 | VLDB | 5.3942942e-05 |
| 11,126 | Dynamic Pruning for Recursive Joins | 2025 | SIGMOD | 4.9793485e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 387 | The LDBC Social Network Benchmark: Interactive Workload | 2015 | SIGMOD | 0.00019426275 |
| 442 | Differential dataflow | 2013 | CIDR | 0.00018210463 |
| 1,045 | Graphflow: An Active Graph Database | 2017 | SIGMOD | 0.00012322402 |
| 2,257 | Regular Path Query Evaluation on Streaming Graphs | 2020 | SIGMOD | 8.7434588e-05 |
| 5,684 | iTurboGraph: Scaling and Automating Incremental Graph Analytics | 2021 | SIGMOD | 6.0391416e-05 |
| 8,980 | Graphsurge: Graph Analytics on View Collections Using Differential Computation | 2021 | SIGMOD | 5.2437006e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 1,551 | Multiple Query Processing in Deductive Databases using Query Graphs | 1986 | VLDB |
| 2 | 5,867 | Scaling-Up In-Memory Datalog Processing: Observations and Techniques | 2019 | VLDB |
| 3 | 10,638 | Enabling Efficient Direct Update on Rule-Based Compressed Graph | 2026 | SIGMOD |
| 4 | 812 | The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates | 2017 | SIGMOD |
| 5 | 442 | Differential dataflow | 2013 | CIDR |
| 6 | 3,204 | Columnar Storage and List-based Processing for Graph Database Management Systems | 2021 | VLDB |
| 7 | 5,584 | Efficient Main Memory Data Management Using the DBGraph Storage Model | 1990 | VLDB |
| 8 | 7,292 | Computing the Difference of Conjunctive Queries Efficiently | 2023 | SIGMOD |
| 9 | 1,249 | Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows | 2018 | VLDB |
| 10 | 9,980 | Schema-Based Query Optimisation for Graph Databases | 2025 | SIGMOD |