# Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2024.

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

- [MemoTime: Memory-Augmented Temporal Knowledge Graph Enhanced Large Language Model Reasoning](https://mlsanity.com/paper/2510.13614/) (2025)
- [Cornerstones or Stumbling Blocks? Deciphering the Rock Tokens in On-Policy Distillation](https://mlsanity.com/paper/2605.09253/) (2026)
- [PRoH: Dynamic Planning and Reasoning over Knowledge Hypergraphs for Retrieval-Augmented Generation](https://mlsanity.com/paper/2510.12434/) (2025)
- [HyperJoin: LLM-augmented Hypergraph Link Prediction for Joinable Table Discovery](https://mlsanity.com/paper/2601.01015/) (2026)
- [Beyond Homophily: Community Search on Heterophilic Graphs](https://mlsanity.com/paper/2601.01703/) (2026)
- [COL-Trees: Efficient Hierarchical Object Search in Road Networks](https://mlsanity.com/paper/2601.22183/) (2026)

## Abstract (arXiv)

Top-k Nearest Neighbors (kNN) problem on road network has numerous applications on location-based services. As direct search using the Dijkstra's algorithm results in a large search space, a plethora of complex-index-based approaches have been proposed to speedup the query processing. However, even with the current state-of-the-art approach, long query processing delays persist, along with significant space overhead and prohibitively long indexing time. In this paper, we depart from the complex index designs prevalent in existing literature and propose a simple index named KNN-Index. With KNN-Index, we can answer a kNN query optimally and progressively with small and size-bounded index. To improve the index construction performance, we propose a bidirectional construction algorithm which can effectively share the common computation during the construction. Theoretical analysis and experimental results on real road networks demonstrate the superiority of KNN-Index over the state-of-the-art approach in query processing performance, index size, and index construction efficiency.