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

• URL: http://arxiv.org/abs/2602.04068v1
• Date: Tue, 03 Feb 2026 23:08:25 GMT
• Title: An Empirical Survey and Benchmark of Learned Distance Indexes for Road Networks
• Abstract summary: computation of shortest-path distances in road networks is a core operation in navigation systems, location-based services, and spatial analytics.<n>Numerous distance indexes have been proposed to speed up query processing for shortest distance queries.<n>With the advancement in machine learning (ML), researchers have designed and proposed ML-based distance indexes to answer approximate shortest path and distance queries efficiently.<n>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.
• Score: 4.738824512722185
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 the advancement 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 seven real-world road networks and workload-driven query datasets derived from trajectory data, we benchmark ten representative ML techniques and compare them against strong 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 distance indexes.

Related papers

• LLM-Aided A* Search in Non-Geometric Network Graphs [0.4078247440919473]
  We propose a large language model (LLM)-aided A* algorithm in which an LLM generates intermediate waypoints that guide the A* expansion toward promising graph regions.<n>Our experiments on multiple graph topologies with up to 2,000 nodes demonstrate that LLM reduce the number of expanded nodes by around 50% while incurring only a marginal path cost increase compared to the optimal solution.
  arXiv  Detail & Related papers  (2026-06-22T10:26:35Z)
• Route Before Retrieve: Activating Latent Routing Abilities of LLMs for RAG vs. Long-Context Selection [57.3886742625188]
  Pre-Route is a proactive routing framework that performs structured reasoning before answering.<n>Our study shows three key findings: (i) LLMs possess latent routing ability that can be reliably elicited with guidelines; (ii) linear probes reveal that structured prompts sharpen the separability of the "optimal routing" in representation space; and (iii) distillation transfers this reasoning structure to smaller models for lightweight deployment.
  arXiv  Detail & Related papers  (2026-05-11T09:10:55Z)
• CompassLLM: A Multi-Agent Approach toward Geo-Spatial Reasoning for Popular Path Query [10.085519288797345]
  We introduce CompassLLM, a novel multi-agent framework to solve the popular path query.<n> CompassLLM employs its agents in a two-stage pipeline: the SEARCH stage that identifies popular paths, and the GENERATE stage that synthesizes novel paths in the absence of an existing one in the historical trajectory data.
  arXiv  Detail & Related papers  (2025-10-08T20:28:52Z)
• Approximate Nearest Neighbour Search on Dynamic Datasets: An Investigation [20.409659920455955]
  Approximate k-Nearest Neighbour (ANN) methods are often used for mining information and aiding machine learning on large scale high-dimensional datasets.<n>For applications with static datasets, runtime constraints and dataset properties can be used to empirically select an ANN method with suitable operating characteristics.<n>Traditional evaluation approaches do not consider the computational costs of updating the index structure, as well as the rate and size of index updates.
  arXiv  Detail & Related papers  (2024-04-30T06:21:44Z)
• Minimally Supervised Learning using Topological Projections in Self-Organizing Maps [55.31182147885694]
  We introduce a semi-supervised learning approach based on topological projections in self-organizing maps (SOMs) Our proposed method first trains SOMs on unlabeled data and then a minimal number of available labeled data points are assigned to key best matching units (BMU) Our results indicate that the proposed minimally supervised model significantly outperforms traditional regression techniques.
  arXiv  Detail & Related papers  (2024-01-12T22:51:48Z)
• Learning Graph Search Heuristics [48.83557172525969]
  We present PHIL (Path Heuristic with Imitation Learning), a novel neural architecture and a training algorithm for discovering graph search and navigations from data. Our function learns graph embeddings useful for inferring node distances, runs in constant time independent of graph sizes, and can be easily incorporated in an algorithm such as A* at test time. Experiments show that PHIL reduces the number of explored nodes compared to state-of-the-art methods on benchmark datasets by 58.5% on average.
  arXiv  Detail & Related papers  (2022-12-07T22:28:00Z)
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
  We propose a Laplacian enhanced low-rank tensor (LETC) framework featuring both lowrankness and multi-temporal correlations for large-scale traffic speed kriging. We then design an efficient solution algorithm via several effective numeric techniques to scale up the proposed model to network-wide kriging.
  arXiv  Detail & Related papers  (2022-10-21T07:25:57Z)
• Training Robust Deep Models for Time-Series Domain: Novel Algorithms and Theoretical Analysis [32.45387153404849]
  We propose a novel framework referred as RObust Training for Time-Series (RO-TS) to create robust DNNs for time-series classification tasks. We show the generality and advantages of our formulation using the summation structure over time-series alignments. Our experiments on real-world benchmarks demonstrate that RO-TS creates more robust DNNs when compared to adversarial training.
  arXiv  Detail & Related papers  (2022-07-09T17:21:03Z)
• Efficient Nearest Neighbor Language Models [114.40866461741795]
  Non-parametric neural language models (NLMs) learn predictive distributions of text utilizing an external datastore. We show how to achieve up to a 6x speed-up in inference speed while retaining comparable performance.
  arXiv  Detail & Related papers  (2021-09-09T12:32:28Z)
• Real-Time Visual Object Tracking via Few-Shot Learning [107.39695680340877]
  Visual Object Tracking (VOT) can be seen as an extended task of Few-Shot Learning (FSL) We propose a two-stage framework that is capable of employing a large variety of FSL algorithms while presenting faster adaptation speed. Experiments on the major benchmarks, VOT2018, OTB2015, NFS, UAV123, TrackingNet, and GOT-10k are conducted, demonstrating a desirable performance gain and a real-time speed.
  arXiv  Detail & Related papers  (2021-03-18T10:02:03Z)
• Road Network Metric Learning for Estimated Time of Arrival [93.0759529610483]
  In this paper, we propose the Road Network Metric Learning framework for Estimated Time of Arrival (ETA) It consists of two components: (1) a main regression task to predict the travel time, and (2) an auxiliary metric learning task to improve the quality of link embedding vectors. We show that our method outperforms the state-of-the-art model and the promotion concentrates on the cold links with few data.
  arXiv  Detail & Related papers  (2020-06-24T04:45:14Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  We present a scalable approach for range and $k$ nearest neighbor queries under computationally expensive metrics. Based on clustering for metric indexes, we obtain a dynamic tree structure whose size is linear in the number of trajectories. We analyze the efficiency and effectiveness of our methods with extensive experiments on diverse synthetic and real-world data sets.
  arXiv  Detail & Related papers  (2020-05-28T04:12:43Z)
• Deep Learning based Pedestrian Inertial Navigation: Methods, Dataset and On-Device Inference [49.88536971774444]
  Inertial measurements units (IMUs) are small, cheap, energy efficient, and widely employed in smart devices and mobile robots. Exploiting inertial data for accurate and reliable pedestrian navigation supports is a key component for emerging Internet-of-Things applications and services. We present and release the Oxford Inertial Odometry dataset (OxIOD), a first-of-its-kind public dataset for deep learning based inertial navigation research.
  arXiv  Detail & Related papers  (2020-01-13T04:41:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.