Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (15): 6-8.

• 博士论坛 • Previous Articles     Next Articles

Non-recursive KNN search using depth-first traversal of Δ-tree

LIU Yan1,2,HAO Zhongxiao1,3   

  1. 1.College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China
    2.Institute of Software,Changchun University,Changchun 130022,China
    3.College of Computer Science and Technology,Harbin Institute of Technology,Harbin 150001,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-05-21 Published:2011-05-21


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

  1. 1.哈尔滨理工大学 计算机科学与技术学院,哈尔滨 150080
    2.长春大学 软件学院,长春 130022
    3.哈尔滨工业大学 计算机科学与技术学院,哈尔滨 150001

Abstract: k Nearest Neighbor(kNN) search is one of the most important operations in high databases.Although it has received considerable attention in the database literature,there is little prior work on kNN retrieval in main-memory databases.Fully utilizing its own characteristics of kNN query,a new kNN search algorithm is proposed,called NR_DF_knn_Search,for efficient main memory index Δ-tree.This algorithm searches the leaf nodes of Δ-tree that nearer the query point by non-recursive depth first manner,can quickly find near optimal kNN candidates,update pruning distance,increase prune force,narrow the search space,so it improves kNN query efficiency.Extensive experiments are conducted to evaluate the NR_DF_knn_Search algorithm,and report results demonstrate its effectiveness.

Key words: high-dimensional index, main-memory kNN search, non-recursive, Nearest Neighbor(NN) search, depth-first search

摘要: kNN查询是高维数据库中最重要的操作之一,尽管它在数据库研究中得到了极大的关注,但很少有关于主存数据库kNN查询的工作。充分利用kNN查询自身的特点,基于高效的主存索引Δ-tree设计了一种新的kNN查询算法NR_DF_knn_Search,该算法采用非递归方式深度优先搜索Δ-tree中距离查询点较近的叶子节点,能够快速找到较优的kNN候选,更新修剪距离,加大剪枝力度,缩小搜索空间,从而提高kNN查询效率。通过实验对该算法进行了估价,结果证明该算法是有效的。

关键词: 高维索引, 主存kNN查询, 非递归, 最近邻查询, 深度优先搜索