Query Preserving Graph Compression
Summary: Query-preserving graph compression: compute Gr from G so that for any Q in a user class Q, Q(G) = Q'(Gr) with Q' efficiently computable, enabling direct evaluation of Q on Gr without decompression. Approach uses reachability equivalence and graph bisimulation (bounded simulation) for reachability and pattern queries; incremental maintenance costs depend only on Delta G and Gr (not on G); experiments report ~95% reduction for reachability and ~57% for graph-pattern queries. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Wenfei Fan (Harbin Engineering University; University of Edinburgh)
- 2. Jianzhong Li (Harbin Engineering University)
- 3. Xin Wang (University of Edinburgh)
- 4. Yinghui Wu (University of California Santa Barbara; University of Edinburgh)
BibTeX Citation
@inproceedings{fan_sigmod12,
title = {{Query Preserving Graph Compression}},
author = {Fan, Wenfei and Li, Jianzhong and Wang, Xin and Wu, Yinghui},
series = {{SIGMOD} '12},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2213836.2213855},
url = {https://dl.acm.org/doi/10.1145/2213836.2213855},
year = {2012}
}Incoming Citations (Sorted by Pagerank)
Showing 25 of 25 citing papers.
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 8 of 8 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 274 | 3-HOP: A High-Compression Indexing Scheme for Reachability Query | 2009 | SIGMOD | 0.00022490994 |
| 563 | Graph Summarization with Bounded Error | 2008 | SIGMOD | 0.00016327158 |
| 693 | GRAIL: Scalable Reachability Index for Large Graphs | 2010 | VLDB | 0.00014734389 |
| 774 | Efficiently Answering Reachability Queries on Very Large Directed Graphs | 2008 | SIGMOD | 0.00014083518 |
| 1,023 | D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data | 2003 | SIGMOD | 0.00012432693 |
| 1,148 | Graph Pattern Matching: From Intractable to Polynomial Time | 2010 | VLDB | 0.00011809728 |
| 1,329 | A Memory Efficient Reachability Data Structure Through Bit Vector Compression | 2011 | SIGMOD | 0.00011000029 |
| 2,525 | Path Queries on Compressed XML | 2003 | VLDB | 8.343313e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 7,840 | DAG Reduction: Fast Answering Reachability Queries | 2017 | SIGMOD |
| 2 | 1,849 | Reachability Queries on Large Dynamic Graphs: A Total Order Approach | 2014 | SIGMOD |
| 3 | 563 | Graph Summarization with Bounded Error | 2008 | SIGMOD |
| 4 | 2,851 | Incremental Graph Computations: Doable and Undoable | 2017 | SIGMOD |
| 5 | 7,015 | A Hierarchical Contraction Scheme for Querying Big Graphs | 2022 | SIGMOD |
| 6 | 1,329 | A Memory Efficient Reachability Data Structure Through Bit Vector Compression | 2011 | SIGMOD |
| 7 | 6,526 | CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression | 2023 | SIGMOD |
| 8 | 10,638 | Enabling Efficient Direct Update on Rule-Based Compressed Graph | 2026 | SIGMOD |
| 9 | 5,554 | Making Graphs Compact by Lossless Contraction | 2021 | SIGMOD |
| 10 | 4,551 | Querying Big Graphs within Bounded Resources | 2014 | SIGMOD |