A Hierarchical Contraction Scheme for Querying Big Graphs
Summary: Hierarchical contraction for single-machine graph queries; contract subgraphs into supernodes to form an in-memory hierarchy with per-Q synopses. Maintains bounded incremental updates; demonstrates exact answers with 7.6% memory and 9.8x speedups, up to 120x vs 6-machine parallel systems. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Wenfei Fan (Beihang University; Shenzhen University; University of Edinburgh)
- 2. Yuanhao Li (University of Edinburgh)
- 3. Muyang Liu (University of Edinburgh)
- 4. Can Lu (Shenzhen University)
BibTeX Citation
@inproceedings{fan_sigmod22,
title = {{A Hierarchical Contraction Scheme for Querying Big Graphs}},
author = {Fan, Wenfei and Li, Yuanhao and Liu, Muyang and Lu, Can},
series = {{SIGMOD} '22},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3514221.3517862},
url = {https://dl.acm.org/doi/10.1145/3514221.3517862},
year = {2022}
}
Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,408 | CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression | 2023 | SIGMOD | 5.8842681e-05 |
| 8,504 | Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries | 2024 | VLDB | 5.4132367e-05 |
| 10,376 | GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries | 2026 | SIGMOD | 5.093636e-05 |
| 11,236 | Improving Graph Compression for Efficient Resource-Constrained Graph Analytics | 2024 | VLDB | 5.093636e-05 |
| 11,241 | Poligras: Policy-based Graph Summarization | 2024 | VLDB | 5.093636e-05 |
| 11,425 | Homomorphic Compression: Making Text Processing on Compression Unlimited | 2023 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 23 of 23 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 5,784 | Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks | 2021 | SIGMOD |
| 2 | 1,998 | A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries | 2017 | PODS |
| 3 | 2,678 | Weighted Hypertree Decompositions and Optimal Query Plans | 2004 | PODS |
| 4 | 442 | Efficient Subgraph Matching on Billion Node Graphs | 2012 | VLDB |
| 5 | 2,798 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD |
| 6 | 5,370 | Diversified Top-k Subgraph Querying in a Large Graph | 2016 | SIGMOD |
| 7 | 1,336 | Query Preserving Graph Compression | 2012 | SIGMOD |
| 8 | 7,380 | MiniGraph: Querying Big Graphs with a Single Machine | 2023 | VLDB |
| 9 | 5,415 | Making Graphs Compact by Lossless Contraction | 2021 | SIGMOD |
| 10 | 4,474 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD |