Succinct Graph Representations as Distance Oracles: An Experimental Evaluation

Summary: Empirically compares 12 exact distance oracles from embeddings and other succinct representations across graphs. Embeddings offer fast setup and structured-graph accuracy; unstructured graphs degrade; GOSH-based approximations scale to 100M+ nodes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12911
Venue: VLDB
Year: 2022
Pagerank: 5.093636e-05
Overall Rank: 11,574 | 20.60%
DOI: 10.14778/3551793.3551794

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Arpit Merchant (University of Helsinki)
2. Aristides Gionis (KTH Royal Institute of Technology)
3. Michael Mathioudakis (University of Helsinki)

BibTeX Citation

@article{merchant_vldb22,
        title = {{Succinct Graph Representations as Distance Oracles: An Experimental Evaluation}},
        author = {Merchant, Arpit and Gionis, Aristides and Mathioudakis, Michael},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {11},
        pages = {2297--2306},
        doi = {10.14778/3551793.3551794},
        url = {https://doi.org/10.14778/3551793.3551794},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1,309	An Experimental Study on Hub Labeling based Shortest Path Algorithms	2018	VLDB	0.00011210911
2,152	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	9.0778596e-05
3,828	FREDE: Anytime Graph Embeddings	2021	VLDB	7.0903874e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,857	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD
2	3,278	Simple, Fast, and Scalable Reachability Oracle	2013	VLDB
3	11,143	k-Clustering with Comparison and Distance Oracles	2024	PODS
4	11,993	Distance Oracle on Terrain Surface	2017	SIGMOD
5	5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD
6	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
7	4,572	On the Embeddability of Random Walk Distances	2013	VLDB
8	968	Path Oracles for Spatial Networks	2009	VLDB
9	4,786	Architecture-Intact Oracle for Fastest Path and Time Queries on Dynamic Spatial Networks	2020	SIGMOD
10	7,211	Toward a Distance Oracle for Billion-Node Graphs	2014	VLDB