The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis

Summary: Uses the metric backbone—the minimum subgraph preserving weighted shortest paths—to shrink graphs for exact or approximate analytics. A scalable distributed heuristic removes first-order semi-metric edges, achieving up to 6.7× speedups in Giraph and Neo4j on graphs with 50B edges. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11544
Venue: VLDB
Year: 2016
Pagerank: 5.4577751e-05
Overall Rank: 8,245 | 43.44%
DOI: 10.14778/2947618.2947623

Incoming Non-self Citations Over Time

Authors

1. Vasiliki Kalavri (KTH Royal Institute of Technology)
2. Tiago Simas (Telefonica Research)
3. Dionysios Logothetis (Meta)

BibTeX Citation

@article{kalavri_vldb16,
        title = {{The shortest path is not always a straight line: Leveraging semi-metricity in graph analysis}},
        author = {Kalavri, Vasiliki and Simas, Tiago and Logothetis, Dionysios},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {9},
        pages = {672--683},
        doi = {10.14778/2947618.2947623},
        url = {https://doi.org/10.14778/2947618.2947623},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,871	P2H: Efficient Distance Querying on Road Networks by Projected Vertex Separators	2021	SIGMOD	8.0110616e-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
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
20	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00056944564
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
548	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016694936
1,336	Query Preserving Graph Compression	2012	SIGMOD	0.00011118804

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
2	746	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD
3	9,032	Bonding Vertex Sets Over Distributed Graph: A Betweenness Aware Approach	2015	VLDB
4	1,386	On k-skip Shortest Paths	2011	SIGMOD
5	1,232	A Highway-Centric Labeling Approach for Answering Distance Queries on Large Sparse Graphs	2012	SIGMOD
6	5,678	Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement	2022	VLDB
7	5,208	Efficient Shortest Path Counting on Large Road Networks	2022	VLDB
8	5,571	Hub Labeling for Shortest Path Counting	2020	SIGMOD
9	5,784	Query-by-Sketch: Scaling Shortest Path Graph Queries on Very Large Networks	2021	SIGMOD
10	352	On Graph Query Optimization in Large Networks	2010	VLDB