计算机工程与应用2011，Vol.47Issue(15)：6-8,28,4.DOI:10.3778/j.issn.1002-8331.2011.15.002
深度优先遍历△-tree的非递归KNN查询
Non-recursive KNN search using depth-first traversal of Δ-tree.
摘要
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.关键词
高维索引/主存kNN查询/非递归/最近邻查询/深度优先搜索Key words
high-dimensional index/main-memory kNN search/non-recursive/Nearest Neighbor(NN) search/depth-first search分类
信息技术与安全科学引用本文复制引用
刘艳,郝忠孝..深度优先遍历△-tree的非递归KNN查询[J].计算机工程与应用,2011,47(15):6-8,28,4.基金项目
黑龙江省自然科学基金(the Natural Science Foundation of Heilongjiang Province of China under Grant No.F200601). （the Natural Science Foundation of Heilongjiang Province of China under Grant No.F200601）
