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

Jul 10, 2026

Learning Partition Trees for Nearest Neighbor Search

We study nearest neighbor search from the perspective of data-driven algorithm design: given a dataset P⊂RdP \subset \mathbb{R}^d of size nn and sample access to a query distribution over Rd\mathbb{R}^d, the goal is to learn a data structure optimized for queries drawn from that specific distribution. We focus on the class of balanced halfspace trees, which naturally abstracts space-partitioning frameworks like locality-sensitive hashing. Assuming Gaussian-like marginal conditions on the dataset and query distribution, we give an efficient algorithm that learns a tree achieving o(nd)o(nd) query time, provided that a perfect tree exists. At the core of our algorithmic approach is the balanced halfspace cut problem, where we are given a distribution over Rd×Rd\mathbb{R}^d \times \mathbb{R}^d and must find a balanced halfspace that minimizes the fraction of cut pairs. We prove that without distributional assumptions, finding the optimal balanced halfspace is NP-hard. To circumvent this computational barrier, we design an efficient improper learning algorithm: if the optimal halfspace cuts an αα fraction of pairs, our algorithm outputs a balanced polynomial threshold function of degree O~(1/ε2)\tilde{O}(1/\varepsilon^2) that cuts at most an O(α+ε)O(\sqrt{α+\varepsilon}) fraction.
Oct 12, 2026

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

Nearest neighbor search algorithms are widely used and have a long history, but we find that key implementation details are seldom reviewed in articles about them. These details can materially impact performance, and thus change the conclusions one makes about a given algorithm's superiority. In this article, we highlight these impacts by reviewing the Cover Tree as an example, producing RustKNN, a unified Rust implementation of three construction variants of the Cover Tree with three query modes. Our analysis reveals: (1) the optimal query strategy depends on kk and on the dataset (single-tree search is fastest at k=1k{=}1 on three of our four largest datasets, while dual-tree search is fastest at k≥5k{\ge}5 on the three largest), and choosing the wrong query mode can cost up to a 7.5×7.5\times factor in runtime; (2) the cover tree base parameter, set to 2 in theory and 1.3 in practice, is not a safe default for dual-tree search: 1.3 is optimal on only one of seven datasets, and on covtype it is 1.6×1.6\times slower than the optimum; (3) among five micro-optimizations, only early-exit distance computation has a consistent effect, and that effect grows with dimension (none at d=32d{=}32, 1.31×1.31\times at d=54d{=}54, and 1.49×1.49\times at d=784d{=}784); and (4) all-nearest-neighbor and held-out benchmarks yield different implementation rankings. All main timing tables report medians over 20 independent allocations with bootstrap 95% confidence intervals. RustKNN is open source at https://github.com/CrowdStrike/RustKNN.
Oct 10, 2026

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

Nearest-neighbor (NN) search underlies countless robotics algorithms, but many state spaces are not Euclidean: orientations live on SO(2)SO(2) or SO(3)SO(3) and poses on SE(2)SE(2) or SE(3)SE(3), and a Euclidean KD-tree on their raw coordinates returns wrong neighbors. We present a header-only, dependency-free C++ KD-tree library for exact NN search on user-defined product manifolds declared at compile time: the space is composed from base manifolds (Rn\mathbb{R}^n, SO(2)SO(2), SO(3)SO(3), SnS^n; products SE(2)SE(2), SE(3)SE(3), tori) with a single type alias, and the library synthesizes a metric whose pruning is provably admissible, wrap-aware for circular coordinates and double-cover-aware for unit quaternions. Experiments confirm exactness (recall 1.01.0 vs an exhaustive scan under the same product metric), where the Euclidean-on-raw shortcut collapses to recall ≈0.5m\approx 0.5^{m} for mm rotation blocks, with up to three orders of magnitude speedup over brute force. We further contribute an incremental, self-balancing single-tree index for points under heavy churn (e.g. sliding-window LiDAR maps) or SE(3)SE(3) trajectories: bounded memory and faster updates than prior work, with an optional asynchronous tail-latency-bounding mode. The implementation is open source: https://github.com/jlblancoc/nanoflann