cs.DBJan 28, 2026

COL-Trees: Efficient Hierarchical Object Search in Spatial Networks

Authors: Tenindra Abeywickrama, Muhammad Aamir Cheema, Sabine Storandt

Organizations: Center for Computational Science, RIKEN, Japan · Faculty of Information Technology, Monash University, Australia · Department of Computer and Information Science, University of Konstanz, Germany

Abstract

Many spatial network applications, such as map-based services, rely heavily on efficient methods to search for relevant nearby points-of-interest (POIs). A kk Nearest Neighbor (kkNN) query is one such example that finds the kk closest POIs from an agent's location. While most existing techniques for spatial networks focus on retrieving nearby POIs for a single agent, these search heuristics do not translate to many other applications. For example, Aggregate kk Nearest Neighbor (AkkNN) queries require POIs that are close to multiple agents. kk Farthest Neighbors (kkFN) 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 spatial networks such as road network graphs. 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 AkkNN, kkFN, and other queries. Our experiments evaluate performance on real-world and synthetic datasets including multiple types of spatial networks, such as road networks of varying sizes and edge weights, terrain networks, and 2D physics meshes. The results demonstrate that our techniques significantly outperform existing approaches, achieving up to three orders of magnitude improvement. Moreover, this comes at a small pre-processing overhead in both theory and practice.

Figures & tables

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Learning Partition Trees for Nearest Neighbor Search

    Jul 10, 2026Sanjeev Khanna, Ashwin Padaki, Erik WaingartenExact Nearest Neighbor Search

  2. KNN Implementation Details Can Dramatically Change Performance: An Example from Cover Trees

    Oct 12, 2026Amol Khanna, Edward RaffExact Nearest Neighbor Searchk-Nearest Neighbors

  3. nanoflann: A Header-Only KD-Tree Library for Exact Nearest-Neighbor Search on Compile-Time Product Manifolds

    Oct 10, 2026José Luis Blanco-ClaracoExact Nearest Neighbor SearchTree Search