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: 4520
Venue: SIGMOD
Year: 2012
Pagerank: 0.00011283792
Overall Rank: 1,579 | 89.02%
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.00030040036
444	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00022987918
2,007	Exploiting Vertex Relationships in Speeding up Subgraph Isomorphism over Large Graphs	2015	VLDB	9.8081235e-05
2,607	Graph Stream Summarization: From Big Bang to Big Crunch	2016	SIGMOD	8.4630211e-05
2,997	Subgraph Matching: on Compression and Computation	2018	VLDB	7.7559339e-05
3,143	Extracting and Analyzing Hidden Graphs from Relational Databases	2017	SIGMOD	7.4804326e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
4,761	Efficient Graph Summarization using Weighted LSH at Billion-Scale	2021	SIGMOD	5.9404527e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
4,990	ZipG: A Memory-efficient Graph Store for Interactive Queries	2017	SIGMOD	5.7825419e-05
5,517	Representing Paths in Graph Database Pattern Matching	2023	VLDB	5.4626107e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
5,932	Hub Labeling for Shortest Path Counting	2020	SIGMOD	5.2670741e-05
5,968	Summarizing Static and Dynamic Big Graphs	2017	VLDB	5.2503253e-05
6,730	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	4.9479867e-05
6,985	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8729387e-05
7,596	DAG Reduction: Fast Answering Reachability Queries	2017	SIGMOD	4.7016964e-05
8,070	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.5932982e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.1945683e-05
10,581	Causal DAG Summarization	2025	VLDB	4.1945683e-05
10,674	Improving Time Series Data Compression in Apache IoTDB	2025	VLDB	4.1945683e-05
11,026	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	4.1945683e-05
11,031	Poligras: Policy-based Graph Summarization	2024	VLDB	4.1945683e-05
11,224	Homomorphic Compression: Making Text Processing on Compression Unlimited	2023	SIGMOD	4.1945683e-05
12,097	Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory)	2013	VLDB	4.1945683e-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
279	3-HOP: A High-Compression Indexing Scheme for Reachability Query	2009	SIGMOD	0.00029113513
388	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024662272
733	GRAIL: Scalable Reachability Index for Large Graphs	2010	VLDB	0.00017460741
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
993	D(K)-Index: An Adaptive Structural Summary for Graph-Structured Data	2003	SIGMOD	0.00014765816
1,414	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012118275
1,553	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011402871
2,507	Path Queries on Compressed XML	2003	VLDB	8.6311009e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
1,777	Reachability Queries on Large Dynamic Graphs: A Total Order Approach	2014	SIGMOD	0.00010589591
388	Graph Summarization with Bounded Error	2008	SIGMOD	0.00024662272
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
6,730	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD	4.9479867e-05
1,553	A Memory Efficient Reachability Data Structure Through Bit Vector Compression	2011	SIGMOD	0.00011402871
6,985	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8729387e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05