aiqbench analysis
This research introduces the COL-Tree, a novel hierarchical data structure designed to accelerate complex spatial queries like Aggregate k-Nearest Neighbor in road networks and terrain graphs. By replacing less effective Euclidean heuristics with accurate landmark-based methods, the approach achieves up to three orders of magnitude improvement over existing techniques for map-based services and related applications.
COL-Trees: Efficient Hierarchical Object Search in Spatial Networks
arXiv:2601.22183v2 Announce Type: replace-cross 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 $k$ Nearest Neighbor ($k$NN) query is one such example that finds the $k$ 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 $k$ Nearest Neighbor (A$k$NN) queries require POIs that are close to multiple agents. $k$ Farthest Neighbors ($k$FN) 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 A$k$NN, $k$FN, 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.
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 $k$ Nearest Neighbor ($k$NN) query is one such example that finds the $k$ 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 $k$ Nearest Neighbor (A$k$NN) queries require POIs that are close to multiple agents. $k$ Farthest Neighbors ($k$FN) 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 A$k$NN, $k$FN, 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.
Databases (cs.DB); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS)
arXiv:2601.22183 [cs.DB]
(or arXiv:2601.22183v2 [cs.DB] for this version)
https://doi.org/10.48550/arXiv.2601.22183 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 325 words
Related coverage
Integrated Hierarchical Decision-Making in Inverse Kinematic Planning and Control
arXiv · Jun 9, 2026
HIGS: Hierarchical Implicit Grids for Joint Geometric and Semantic Scene Understanding
arXiv · Oct 1, 2026
TENSO: Software Package for Numerically Exact Open Quantum Dynamics Based on Efficient Tree Tensor Network Decomposition of the Hierarchical Equations of Motion
arXiv · Jun 16, 2026
HiRo: A Compact Four-Directional Hierarchical Reservoir Token-Mixer for Efficient Image Classification
arXiv · Jun 16, 2026