# An Empirical Survey and Benchmark of Learned Distance Indexes for Road Networks

arXiv: https://arxiv.org/abs/2602.04068 · HTML: https://mlsanity.com/paper/2602.04068/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 71 references that are in the map.
- First posted on arXiv 3 Feb 2026.

## Builds on (most cited first, 14 of 14)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [A Survey on Temporal Knowledge Graph: Representation Learning and Applications](https://mlsanity.com/paper/2403.04782/) (2024)
- [DeepTravel: a Neural Network Based Travel Time Estimation Model with Auxiliary Supervision](https://mlsanity.com/paper/1802.02147/) (2018)
- [Graph-based Deep Learning for Communication Networks: A Survey](https://mlsanity.com/paper/2106.02533/) (2021)
- [A Unified Neural Network Approach for Estimating Travel Time and Distance for a Taxi Trip](https://mlsanity.com/paper/1710.04350/) (2017)
- [A Survey of Shortest-Path Algorithms](https://mlsanity.com/paper/1705.02044/) (2017)
- [Shortest path distance approximation using deep learning techniques](https://mlsanity.com/paper/2002.05257/) (2020)
- [Customizable Contraction Hierarchies](https://mlsanity.com/paper/1402.0402/) (2014)
- [Making Fast Graph-based Algorithms with Graph Metric Embeddings](https://mlsanity.com/paper/1906.07040/) (2019)

## Built on by (most cited first, 1 of 1)

- [AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT](https://mlsanity.com/paper/2604.20744/) (2026)

## Abstract (arXiv)

The calculation of shortest-path distances in road networks is a core operation in navigation systems, location-based services, and spatial analytics. Although classical algorithms, e.g., Dijkstra's algorithm, provide exact answers, their latency is prohibitive for modern real-time, large-scale deployments. Over the past two decades, numerous distance indexes have been proposed to speed up query processing for shortest distance queries. More recently, with advances in machine learning (ML), researchers have designed and proposed ML-based distance indexes to answer approximate shortest path and distance queries efficiently. However, a comprehensive and systematic evaluation of these ML-based approaches is lacking. This paper presents the first empirical survey of ML-based distance indexes on road networks, evaluating them along four key dimensions: training time, query latency, storage, and accuracy. Using 13 real-world road networks (7 with workload-driven queries, derived from trajectory data, and 6 with synthetically generated queries), we benchmark ten representative ML techniques and compare them against classical non-ML baselines, highlighting key insights and practical trade-offs. We release a unified open-source codebase to support reproducibility and future research on learned indexes.