COL-Trees：空间网络中的高效分层对象搜索方法
COL-Trees: Efficient Hierarchical Object Search in Spatial Networks
AI 导读
研究者提出新型数据结构 COL-Tree（Compacted Object-Landmark Tree），用更精确的地标式启发方法实现空间网络中的高效分层图遍历，并给出回答 AkNN、kFN 等查询的算法。实验涵盖道路网络、地形网络和 2D 物理网格等真实与合成数据集，性能较现有方法最高提升三个数量级，且预处理开销较小。该工作已提交至 Artificial Intelligence（AIJ）。
正文 · 原文
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.
| Comments: | Submitted to Artificial Intelligence (AIJ) |
| Subjects: | Databases (cs.DB); Artificial Intelligence (cs.AI); Data Structures and Algorithms (cs.DS) |
| Cite as: | arXiv:2601.22183 [cs.DB] |
| (or arXiv:2601.22183v2 [cs.DB] for this version) | |
| https://doi.org/10.48550/arXiv.2601.22183 arXiv-issued DOI via DataCite |
Submission history
From: Tenindra Abeywickrama [view email]
[v1]
Wed, 28 Jan 2026 10:43:38 UTC (445 KB)
[v2]
Wed, 4 Nov 2026 15:00:58 UTC (593 KB)
来源：arXiv cs.AI · arxiv.org