Distributed Graph Simulation: Impossibility and Possibility
Summary: Impossibility: no distributed graph-simulation algorithm can be parallel scalable in either response time or data shipment on fragmented graphs. Partition-bounded guarantees: runtime depends on |Q|, |F_m|, and crossing vertices |V_f|; data shipment depends on |Q| and crossing edges |E_f|, with the first algorithms achieving these bounds and experimental validation; special scalable cases identified. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Wenfei Fan
- 2. Xin Wang
- 3. Yinghui Wu
- 4. Dong Deng
Incoming Citations (Sorted by Pagerank)
Showing 11 of 11 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 444 | Parallelizing Sequential Graph Computations | 2017 | SIGMOD | 0.00022987918 |
| 2,450 | Functional Dependencies for Graphs | 2016 | SIGMOD | 8.7882979e-05 |
| 3,394 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 7.1480446e-05 |
| 4,205 | Association Rules with Graph Patterns | 2015 | VLDB | 6.3597474e-05 |
| 6,730 | A Hierarchical Contraction Scheme for Querying Big Graphs | 2022 | SIGMOD | 4.9479867e-05 |
| 7,004 | RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing | 2024 | VLDB | 4.8656632e-05 |
| 7,279 | Data-driven Visual Graph Query Interface Construction and Maintenance: Challenges and Opportunities | 2016 | VLDB | 4.779057e-05 |
| 8,422 | Deducing Certain Fixes to Graphs | 2019 | VLDB | 4.5167705e-05 |
| 8,715 | Data Driven Approximation with Bounded Resources | 2017 | VLDB | 4.4619052e-05 |
| 10,843 | Machine Learning for Graph Data Management and Query Processing | 2025 | VLDB | 4.1945683e-05 |
| 11,016 | Extending Graph Rules with Oracles | 2024 | VLDB | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 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 |
| 37 | Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud | 2012 | VLDB | 0.0007522744 |
| 1,414 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00012118275 |
| 1,675 | A Distributed Graph Engine for Web Scale RDF Data | 2013 | VLDB | 0.00010947606 |
| 1,720 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00010779343 |
| 2,674 | Minimal MapReduce Algorithms | 2013 | SIGMOD | 8.3328645e-05 |
| 3,402 | TAO: How Facebook Serves the Social Graph | 2012 | SIGMOD | 7.1378698e-05 |
| 5,054 | Performance Guarantees for Distributed Reachability Queries | 2012 | VLDB | 5.7321997e-05 |
| 5,317 | Distributed Query Evaluation with Performance Guarantees | 2007 | SIGMOD | 5.5719038e-05 |
| 5,776 | Capturing Topology in Graph Pattern Matching | 2012 | VLDB | 5.3309758e-05 |
Previous
Page 1 / 1
Next