# COL-Trees: Efficient Hierarchical Object Search in Road Networks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 59 references that are in the map.
- First posted on arXiv 28 Jan 2026.

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

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [The FastMap Algorithm for Shortest Path Computations](https://mlsanity.com/paper/1706.02792/) (2017)
- [Simpler is More: Efficient Top-K Nearest Neighbors Search on Large Road Networks](https://mlsanity.com/paper/2408.05432/) (2024)
- [k-Nearest Neighbors on Road Networks: A Journey in Experimentation and In-Memory Implementation](https://mlsanity.com/paper/1601.01549/) (2016)
- [Hierarchical Cut Labelling -- Scaling Up Distance Queries on Road Networks](https://mlsanity.com/paper/2311.11063/) (2023)
- [Network Farthest-Point Diagrams](https://mlsanity.com/paper/1304.1909/) (2013)
- [Case-Based Subgoaling in Real-Time Heuristic Search for Video Game Pathfinding](https://mlsanity.com/paper/1401.3857/) (2014)
- [Efficient Exact k-Flexible Aggregate Nearest Neighbor Search in Road Networks Using the M-tree](https://mlsanity.com/paper/2106.05620/) (2021)

## Abstract (arXiv)

Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) near a given location. A k Nearest Neighbor (kNN) query is one such example that finds the k closest POIs from an agent's location. While most existing techniques focus on retrieving nearby POIs for a single agent, these search heuristics do not translate to many other applications. For example, Aggregate k Nearest Neighbor (AkNN) queries require POIs that are close to multiple agents. k Farthest Neighbor (kFN) queries require POIs that are the antithesis of nearest. Such problems naturally benefit from a hierarchical approach, but existing methods rely on Euclidean-based heuristics, which have diminished effectiveness in graphs such as road networks. We propose a novel data structure, COL-Tree (Compacted Object-Landmark Tree), to address this gap by enabling efficient hierarchical graph traversal using a more accurate landmark-based heuristic. We then present query algorithms that utilize COL-Trees to efficiently answer AkNN, kFN, and other queries. In our experiments on real-world and synthetic datasets, we demonstrate that our techniques significantly outperform existing approaches, achieving up to 4 orders of magnitude improvement. Moreover, this comes at a small pre-processing overhead in both theory and practice.