深度优先遍历Δ-tree的非递归KNN查询

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

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

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 A-tree.This algorithm searches the leaf nodes of A-tree that nearer the query point by non-recursive depth first manner, can quickly fred 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.