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)

Paper ID: 4582
Venue: SIGMOD
Year: 2012
Pagerank: 0.00011118804
Overall Rank: 1,336 | 90.84%
DOI: 10.1145/2213836.2213855

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.

Rank	Citing Paper	Year	Venue	Pagerank
195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00025813775
956	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.0001297452
1,487	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	0.00010615297
2,148	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	9.0825156e-05
2,187	Subgraph Matching: on Compression and Computation	2018	VLDB	8.9966682e-05
2,854	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	8.0350257e-05
4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.6803983e-05
4,953	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	6.4303691e-05
5,322	ZipG: A Memory-efficient Graph Store for Interactive Queries	2017	SIGMOD	6.2659893e-05
5,370	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	6.2436385e-05
5,415	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	6.2255551e-05
5,418	Representing Paths in Graph Database Pattern Matching	2023	VLDB	6.2255373e-05
5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD	6.1686653e-05
5,751	Summarizing Static and Dynamic Big Graphs	2017	VLDB	6.0994565e-05
6,408	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	5.8842681e-05
6,876	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	5.7483615e-05
7,707	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	5.5636745e-05
8,245	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	5.4577751e-05
9,055	Causal DAG Summarization	2025	VLDB	5.3251649e-05
10,376	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	5.093636e-05
10,923	Improving Time Series Data Compression in Apache IoTDB	2025	VLDB	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
12,294	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	5.093636e-05

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
269	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00022786599
548	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016694936
679	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00015055389
746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00014402233
1,008	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00012688008
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011255351
2,472	Path Queries on Compressed XML	2003	VLDB	8.5327655e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,625	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB
2	1,796	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD
3	548	Graph Summarization with Bounded Error	2008	SIGMOD
4	2,798	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD
5	6,876	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD
6	1,301	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD
7	6,408	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD
8	10,450	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD
9	5,415	Making Graphs Compact by Lossless Contraction	2021	SIGMOD
10	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD