Toward a Distance Oracle for Billion-Node Graphs

Summary: Proposes scalable distance oracles for graphs with billions of nodes using sketch-based encodings. Optimizes landmark selection, distributed BFS, and answer generation to balance space, speed, and accuracy; validated on real and synthetic networks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11126
Venue: VLDB
Year: 2014
Pagerank: 5.6719349e-05
Overall Rank: 7,211 | 50.53%
DOI: 10.14778/2732219.2732225

Incoming Non-self Citations Over Time

Authors

1. Zichao Qi (Tsinghua University)
2. Yanghua Xiao (Fudan University)
3. Bin Shao (Microsoft)
4. Haixun Wang (Microsoft)

BibTeX Citation

@article{qi_vldb14,
        title = {{Toward a Distance Oracle for Billion-Node Graphs}},
        author = {Qi, Zichao and Xiao, Yanghua and Shao, Bin and Wang, Haixun},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {2},
        pages = {61--72},
        doi = {10.14778/2732219.2732225},
        url = {https://doi.org/10.14778/2732219.2732225},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,008	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.8578871e-05
6,844	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.7566172e-05
9,032	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB	5.327953e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
2	4,474	Querying Big Graphs within Bounded Resources	2014	SIGMOD
3	3,857	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD
4	968	Path Oracles for Spatial Networks	2009	VLDB
5	4,786	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD
6	3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB
7	195	Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling	2013	SIGMOD
8	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	11,574	Succinct Graph Representations as Distance Oracles: An Experimental Evaluation	2022	VLDB
10	5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD