基于Δ-tree的递归深度优先KNN查询算法

Recursive Depth-first KNN Query Algorithm Based on Δ-tree

基于Δ-tree提出一种用于高维数据的主存K最近邻(KNN)查询算法。该算法利用递归调用方法深度优先遍历Δ-tree,找到距离查询点较近的叶子节点,并选择其中较优的KNN候选点进行查询,从而缩小修剪距离、提高查询速度。实验结果表明,与已有算法相比,该算法具有更高的查询效率。

This paper proposes an algorithm based on Δ-tree to support efficient main memory K-Nearest Neighbor（KNN） query in high-dimensional databases.By recursive transfer method and depth-first traversal of Δ-tree,the algorithm finds the leaf nodes that are nearer to query point and adopts the superior KNN candidates in them to reduce pruning distance,thus lesses calculation amount and accelerates the nearest neighbors search.Experimental results show that this algorithm can improve query efficiency.