基于有界k-d树的最近点搜索算法

Algorithm for searching nearest-neighbor based on the bounded k-d tree

提出了一种基于有界k-d树的最近点搜索算法.算法的原理是:由根节点中的包围盒确定树中数据的空间范围,并在搜索过程中不断划分包围盒来缩小搜索范围,同时递归地计算查询点到包围盒的距离.结合优先级队列,基于有界k-d树的最近点搜索算法拓展到搜索按距离远近排列的多个最近点.实测和仿真分析表明,本搜索算法的计算效率高于传统的搜索算法.

An algorithm for searching nearest-neighbor is proposed based on the bounded k-d tree of which the spatial range of the data is restricted by the bounded box of the root node.The search area in the searching process is reduced by continually dividing bounded boxes.The distance from a query point to a bounded box is also computed recursively.Combined with a priority queue,the closest point query algorithm can be generalized to search multi-nearest-neighbors ordered by their distances to a query point.The experiments on both real and synthetic data sets show that the query algorithm based on the bounded k-d tree is computationally more efficient than some traditional algorithms.