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 |
|---|---|---|---|---|
| 441 | Parallelizing Sequential Graph Computations | 2017 | SIGMOD | 0.00023172424 |
| 3,439 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD | 7.0916563e-05 |
| 3,478 | Functional Dependencies for Graphs | 2016 | SIGMOD | 7.0554625e-05 |
| 5,120 | Association Rules with Graph Patterns | 2015 | VLDB | 5.6754325e-05 |
| 7,003 | RAGraph: A Region-Aware Framework for Geo-Distributed Graph Processing | 2024 | VLDB | 4.8609956e-05 |
| 7,179 | A Hierarchical Contraction Scheme for Querying Big Graphs | 2022 | SIGMOD | 4.803776e-05 |
| 7,292 | Data-driven Visual Graph Query Interface Construction and Maintenance: Challenges and Opportunities | 2016 | VLDB | 4.7676734e-05 |
| 8,363 | Deducing Certain Fixes to Graphs | 2019 | VLDB | 4.5311185e-05 |
| 8,712 | Data Driven Approximation with Bounded Resources | 2017 | VLDB | 4.4578168e-05 |
| 10,847 | Machine Learning for Graph Data Management and Query Processing | 2025 | VLDB | 4.1905499e-05 |
| 11,019 | Extending Graph Rules with Oracles | 2024 | VLDB | 4.1905499e-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.0019040811 |
| 39 | Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud | 2012 | VLDB | 0.00075263552 |
| 1,419 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00012072488 |
| 1,676 | A Distributed Graph Engine for Web Scale RDF Data | 2013 | VLDB | 0.000109374 |
| 1,806 | Incremental Graph Pattern Matching | 2011 | SIGMOD | 0.00010478244 |
| 2,714 | Minimal MapReduce Algorithms | 2013 | SIGMOD | 8.2426646e-05 |
| 3,399 | TAO: How Facebook Serves the Social Graph | 2012 | SIGMOD | 7.1366107e-05 |
| 5,051 | Performance Guarantees for Distributed Reachability Queries | 2012 | VLDB | 5.7267112e-05 |
| 5,324 | Distributed Query Evaluation with Performance Guarantees | 2007 | SIGMOD | 5.5668659e-05 |
| 5,786 | Capturing Topology in Graph Pattern Matching | 2012 | VLDB | 5.3256482e-05 |
Previous
Page 1 / 1
Next