Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2011, Vol. 37 ›› Issue (22): 48-50. doi: 10.3969/j.issn.1000-3428.2011.22.013

• Networks and Communications • Previous Articles     Next Articles

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

LIU Yan 1,2, HAO Zhong-xiao 1,3   

  1. (1. College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China; 2. Institute of Computer Science and Technology, Changchun University, Changchun 130022, China; 3. College of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China)
  • Received:2011-06-10 Online:2011-11-18 Published:2011-11-20

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

刘 艳 1,2,郝忠孝 1,3   

  1. (1. 哈尔滨理工大学计算机科学与技术学院,哈尔滨 150080;2. 长春大学计算机科学技术学院,长春 130022; 3. 哈尔滨工业大学计算机科学与技术学院,哈尔滨 150001)
  • 作者简介:刘 艳(1981-),女,讲师、博士研究生,主研方向:高维数据处理;郝忠孝,教授、博士生导师
  • 基金资助:
    黑龙江省自然科学基金资助项目(F2006-01)

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: