基于Δ-tree的自底向上的深度递归KNN查询算法  

Δ-tree based bottom-up and deep recursion algorithm of KNN search

作　　者：刘艳[1,2] 郝忠孝[1,3] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080 [2]长春大学软件学院,长春130022 [3]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机应用研究》2011年第8期2889-2892,共4页Application Research of Computers

基　　金：黑龙江省自然科学基金资助项目(F200601)

摘　　要：Δ-tree是一种新提出的多层索引结构,能够加速主存环境中的高维查询。在该高效主存索引的基础上,提出了改进的KNN搜索算法BU_DF_knn_Search,该算法通过定位技术、自底向上、深度优先遍历及过滤策略设计而成,解决了KNN查询中搜索半径未知的难题。在高维数据集上进行了实验,结果显示算法BU_DF_knn_Search比Δ-tree已有的KNN搜索算法具有更高的效率。Δ-tree is a novel multi-level index structure,that can speed up the high-dimensional query in main memory environment.This paper proposed a modified algorithm for main-memory KNN search called BU_DF_knn_Search,which used the efficient main memory index Δ-tree as the underlying index structure.BU_DF_knn_Search was designed through the location technology for query point,bottom up,depth-first search and filtering strategy.It could solve the hard problem that the distance from query point to its k nearest neighbors was unknown apriori and improved the KNN search efficiency.Conducted the experiments on high dimensional datasets.The results illustrate that the proposed algorithm appears to be much faster than the existing KNN search algorithm for main memory index Δ-tree.

关 键 词：高维索引 主存 K最近邻查询 深度优先搜索 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]