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: 6315
Venue: SIGMOD
Year: 2022
Pagerank: 4.803776e-05
Overall Rank: 7,179 | 50.11%
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,983	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8682622e-05
9,486	Enabling Window-Based Monotonic Graph Analytics with Reusable Transitional Results for Pattern-Consistent Queries	2024	VLDB	4.3300131e-05
10,085	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	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

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
39	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00075263552
320	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00027574254
435	Efficient Aggregation for Graph Summarization	2008	SIGMOD	0.00023268266
441	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00023172424
570	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019895021
749	TurboISO: Towards UltraFast and Robust Subgraph Isomorphism Search in Large Graph Databases	2013	SIGMOD	0.00017193776
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
787	Cypher: An Evolving Query Language for Property Graphs	2018	SIGMOD	0.00016624372
964	G-CORE: A Core for Future Graph Query Languages	2018	SIGMOD	0.00014967208
1,040	Querying Graph Databases	2013	PODS	0.00014483577
1,572	Query Preserving Graph Compression	2012	SIGMOD	0.00011296109
3,221	Landmark Indexing for Evaluation of Label-Constrained Reachability Queries	2017	SIGMOD	7.3541078e-05
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
3,478	Functional Dependencies for Graphs	2016	SIGMOD	7.0554625e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05
5,120	Association Rules with Graph Patterns	2015	VLDB	5.6754325e-05
6,119	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.1991813e-05
7,061	Querying Big Data by Accessing Small Data	2015	PODS	4.8400281e-05
7,673	LA3: A Scalable Link- and Locality-Aware Linear Algebra-Based Graph Analytics System	2018	VLDB	4.6772845e-05
7,926	Data Management for Social Networking	2016	PODS	4.6107647e-05
8,963	An Effective Syntax for Bounded Relational Queries	2016	SIGMOD	4.4165156e-05
9,577	Querying Shared Data with Security Heterogeneity	2020	SIGMOD	4.3206631e-05
11,793	BEAS: Bounded Evaluation of SQL Queries	2017	SIGMOD	4.1905499e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,144	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD	5.1865526e-05
2,856	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0120856e-05
1,039	Weighted Hypertree Decompositions and Optimal Query Plans	2004	PODS	0.00014488271
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
3,439	Incremental Graph Computations: Doable and Undoable	2017	SIGMOD	7.0916563e-05
5,903	Diversified Top-k Subgraph Querying in a Large Graph	2016	SIGMOD	5.2757528e-05
1,572	Query Preserving Graph Compression	2012	SIGMOD	0.00011296109
8,152	MiniGraph: Querying Big Graphs with a Single Machine	2023	VLDB	4.5711161e-05
4,207	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3519481e-05
5,030	Making Graphs Compact by Lossless Contraction	2021	SIGMOD	5.7445683e-05