Abstract:
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.
Key words:
high-dimensional index,
main memory,
K-Nearest Neighbor(KNN) query,
depth-first search
摘要: 基于Δ-tree提出一种用于高维数据的主存K最近邻(KNN)查询算法。该算法利用递归调用方法深度优先遍历Δ-tree,找到距离查询点较近的叶子节点,并选择其中较优的KNN候选点进行查询,从而缩小修剪距离、提高查询速度。实验结果表明,与已有算法相比,该算法具有更高的查询效率。
关键词:
高维索引,
主存,
K最近邻查询,
深度优先搜索
CLC Number:
LIU Yan, HAO Zhong-Xiao. Recursive Depth-first KNN Query Algorithm Based on Δ-tree[J]. Computer Engineering, 2011, 37(22): 48-50.
刘艳, 郝忠孝. 基于Δ-tree的递归深度优先KNN查询算法[J]. 计算机工程, 2011, 37(22): 48-50.