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)

Paper ID: 6314
Venue: SIGMOD
Year: 2022
Pagerank: 4.9479867e-05
Overall Rank: 6,730 | 53.19%
DOI: 10.1145/3514221.3517862

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,985	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8729387e-05
9,484	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3341665e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	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

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.

Rank	Cited Paper	Year	Venue	Pagerank
37	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.0007522744
320	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00027577867
435	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00023260172
444	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00022987918
574	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019883211
764	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017018712
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
789	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016634256
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.0001497475
1,037	Querying Graph Databases	2013	PODS	0.00014502493
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
2,450	Functional Dependencies for Graphs	2016	SIGMOD	8.7882979e-05
3,213	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3669794e-05
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
4,205	Association Rules with Graph Patterns	2015	VLDB	6.3597474e-05
4,836	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.8896897e-05
6,146	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.1857597e-05
7,085	Querying Big Data by Accessing Small Data	2015	PODS	4.8388174e-05
7,652	LA3: A Scalable Link- and Locality-Aware Linear Algebra-Based Graph Analytics System	2018	VLDB	4.6875579e-05
7,998	Data Management for Social Networking	2016	PODS	4.6101889e-05
8,961	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4206115e-05
9,578	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	4.3248081e-05
11,785	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,138	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1915368e-05
2,849	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0195487e-05
1,038	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014492414
651	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018648572
3,394	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.1480446e-05
5,854	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.3006473e-05
1,579	Query Preserving Graph Compression	2012	SIGMOD	0.00011283792
8,146	MiniGraph: Querying Big Graphs with a Single Machine	2023	VLDB	4.5755031e-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