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: 4521
Venue: SIGMOD
Year: 2012
Pagerank: 0.00011296109
Overall Rank: 1,572 | 89.08%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030020929
441	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00023172424
2,021	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.7730473e-05
2,609	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4587236e-05
2,963	Subgraph Matching: on Compression and Computation	2018	VLDB	7.8061004e-05
3,147	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4825501e-05
4,207	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3519481e-05
4,758	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	5.9347454e-05
4,987	ZipG: A Memory-efficient Graph Store for Interactive Queries	2017	SIGMOD	5.7769841e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
5,527	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4573655e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
5,933	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2620152e-05
5,975	Summarizing Static and Dynamic Big Graphs	2017	VLDB	5.2452824e-05
6,983	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8682622e-05
7,179	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	4.803776e-05
7,595	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.6980168e-05
8,074	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.58889e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1905499e-05
10,590	Causal DAG Summarization	2025	VLDB	4.1905499e-05
10,682	Improving Time Series Data Compression in Apache IoTDB	2025	VLDB	4.1905499e-05
11,029	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	4.1905499e-05
11,034	Poligras: Policy-based Graph Summarization	2024	VLDB	4.1905499e-05
11,226	Homomorphic Compression: Making Text Processing on Compression Unlimited	2023	SIGMOD	4.1905499e-05
12,105	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.1905499e-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
280	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029092277
387	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024682268
727	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017462279
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014759406
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
1,551	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011395294
2,509	Path Queries on Compressed XML	2003	VLDB	8.6250598e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,969	Leveraging Graph Dimensions in Online Graph Search	2015	VLDB	4.1905499e-05
1,776	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.0001058029
387	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024682268
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
7,179	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	4.803776e-05
1,551	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011395294
6,983	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8682622e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1905499e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
4,207	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3519481e-05