Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks

Summary: Introduces Query-by-Sketch (QbS) for exact shortest-path-graph queries on massive networks, using offline labels to guide online sketch. Proves correctness/complexity; 12 datasets (up to 1.7B vertices, 7.8B edges) yield microseconds on million-scale and sub-second on billion-scale. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6106
Venue: SIGMOD
Year: 2021
Pagerank: 5.1915368e-05
Overall Rank: 6,138 | 57.30%
DOI: 10.1145/3448016.3452826

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
7,441	BatchHL: Answering Distance Queries on Batch-Dynamic Networks at Scale	2022	SIGMOD	4.7302202e-05
8,256	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.5490743e-05
8,668	Towards Generating Hop-constrained s-t Simple Path Graphs	2023	SIGMOD	4.4718257e-05
10,467	Accelerating Skyline Path Enumeration with a Core Attribute Index on Multi-attribute Graphs	2025	SIGMOD	4.1945683e-05
10,571	Quantum Data Management in the NISQ Era	2025	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
376	TEDI: Efficient Shortest Path Query Answering on Graphs	2010	SIGMOD	0.00025097452
945	Path Oracles for Spatial Networks	2009	VLDB	0.00015137526
1,170	Shortest Path and Distance Queries on Road Networks: An Experimental Evaluation	2012	VLDB	0.00013511856
1,838	IS-LABEL: an Independent-Set based Labeling Scheme for Point-to-Point Distance Querying	2013	VLDB	0.00010349881

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,070	The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis	2016	VLDB	4.5932982e-05
6,795	Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond	2020	VLDB	4.9242446e-05
2,437	gSketch: On Query Estimation in Graph Streams	2012	VLDB	8.8231651e-05
9,483	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	4.3341665e-05
788	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016650034
4,211	Querying Big Graphs within Bounded Resources	2014	SIGMOD	6.3563454e-05
8,256	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB	4.5490743e-05
260	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD	0.00030040036
7,236	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB	4.7932355e-05
506	On Graph Query Optimization in Large Networks	2010	VLDB	0.00021475362