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

《2022年深度优先遍历Δ-tree的非递归KNN查询 .pdf》由会员分享，可在线阅读，更多相关《2022年深度优先遍历Δ-tree的非递归KNN查询 .pdf（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、Computer Engineering and Applications 计算机工程与应用2011， 47 （15）1引言在高维数据库中查找与给定查询对象相似的对象是使用频率高但代价昂贵的操作，取回 k个最相似对象的k最近邻查询是其中的最重要的操作。学者们对解决最近邻搜索问题做了很多研究， 但大多数是基于磁盘的。随着主存价格的不断下降，使得将数据库和索引装入主存成为可能，文献 1-2 提出了主存索引 -tree来处理高维kNN 查询，文献 3-5 基于 -tree提出了自相似连接和KNN 连接算法。在kNN 查询中，查询点到它的 kNN 的距离是未知的， 导致修剪距离无先验知识可用，造成了

2、kNN 查询的困难。使用D-tree 进行 kNN 查询时，如果能够尽快缩小修剪距离，将加强过滤、 减少不必要的计算，有利于提高 kNN 查询的效率。本文修改了文献1-2 中为 -tree设计的 kNN 查询算法 KNNSearch， 对 -tree进行基于排序的深度优先遍历，该算法能够克服kNN 查询的自身困难， 快速缩短修剪距离，减小搜索空间， 降低距离计算量， 提高 kNN 查询效率。实验显示本文提出的算法NR_DF_ knn_Search在性能上优于算法 KNNSearch。2基础知识 -tree是一种多层主存索引树，树的每一层采用不同的维度表示数据空间， 节点的维度呈递增形式，根节点

3、使用的维度最少， 而叶子节点的维度最大（全维） 。 -tree使用 PCA 技术对原始数据进行降维， 减少了距离计算代价和缓存丢失1-2。对一个给定的数据集，文献 1-2 采用自顶向下的方式创建 -tree， 算法的主要步骤如下：步骤 1 利用函数 PCA （ ） 将数据集转换到PCA 空间，使用转换后的点集初始化聚类pC。步骤 2 根据 PCA 的信息初始化根节点root 的特征矩阵Eigenmatrix 、 维度向量 m和层数 L 参数。步骤 3 调用递归函数R_insert（node， pC， lev ）确定 -tree深度优先遍历 -tree 的非递归 KNN 查询刘艳1， 2， 郝忠

4、孝1， 3LIUYan1， 2， HAOZhongxiao1， 31.哈尔滨理工大学计算机科学与技术学院， 哈尔滨1500802.长春大学软件学院，长春1300223.哈尔滨工业大学计算机科学与技术学院， 哈尔滨1500011.College of Computer Science and Technology， Harbin Universityof Science and Technology， Harbin 150080， China2.Institute of Software， Changchun University ， Changchun 130022， China3.Colle

5、ge of Computer Science and Technology， Harbin Institute of Technology， Harbin 150001， ChinaLIUYan， HAOZhongxiao.Non-recursiveKNNsearchusingdepth-firsttraversalof -tree.ComputerEngineeringandApplications ， 2011， 47 （15 ） ： 6-8.Abstract ： k Nearest Neighbor（kNN） search is one of the most important ope

6、rations in high databases.Although ithas re-ceived considerable attention in the database literature， there is littleprior workon kNN retrieval in main-memorydatabases.Fullyutilizingits own characteristics of kNN query， a new kNN search algorithmis proposed， called NR_DF_knn_Search， forefficientmain

7、 memory index -tree.This algorithmsearches the leaf nodes of -tree that nearer the query point by non-recur-sive depth first manner， can quickly find near optimal kNN candidates， update pruning distance， increase prune force， narrow thesearch space ， so it improves kNN query efficiency.Extensiveexpe

8、riments are conducted to evaluate the NR_DF_ knn_Search al-gorithm ， 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查

9、询的工作。充分利用kNN 查询自身的特点， 基于高效的主存索引 -tree设计了一种新的kNN 查询算法 NR_DF_ knn_Search， 该算法采用非递归方式深度优先搜索 -tree中距离查询点较近的叶子节点，能够快速找到较优的kNN 候选，更新修剪距离， 加大剪枝力度，缩小搜索空间， 从而提高 kNN 查询效率。通过实验对该算法进行了估价，结果证明该算法是有效的。关键词：高维索引；主存 kNN 查询； 非递归；最近邻查询；深度优先搜索DOI ： 10.3778/j.issn.1002-8331.2011.15.002文章编号：1002-8331 （2011 ） 15-0006-03文献

10、标识码：A中图分类号：TP311.13基金项目： 黑龙江省自然科学基金（the NaturalScience Foundationof HeilongjiangProvinceof Chinaunder Grant No.F200601 ） 。作者简介： 刘艳 （1981） ， 女， 博士研究生，主要研究领域为高维相似连接和相似搜索；郝忠孝（1940） ， 男， 博导， 教授。 E-mail ： 收稿日期： 2011-01-11 ； 修回日期： 2011-03-216名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

11、- - - - - - - 第 1 页，共 3 页 - - - - - - - - - 2011， 47 （15 ）中第 lev层节点 node中各项的内容， 每个子聚类对应一项。其中， 函数 R_insert （node， pC， lev ） 使用前 mlev维通过 k-means算法将聚类pC划分为 k个子聚类， 将每个子聚类的中心和半径信息添加到相应的项中，如果子聚类中点的数目能够装入叶子节点， 则直接将点插入到叶子节点中，否则递归调用R_insert （ ） 构建树的下一层。本文根据文献 1-2 中创建 -tree的方法，为数据集 R创建 -tree。定义 1 （孩子节点的序号 ）对

12、-tree中内部节点的各孩子节点从左到右使用1， 2， 3， 进行编号， 用以表示各孩子节点为其父节点的第几个孩子节点的序号，简称孩子节点的序号。定义 2 （查询点与节点之间的距离） 查询点到节点中心的距离与节点半径之差， 称为查询点与节点之间的距离。定理 1 转换后的低维 PCA6空间中查询点到 -tree中节点之间的距离是高维空间中查询点到该节点中所有数据点之间距离的下限，如果在低维 PCA 空间中查询点到 -tree中节点之间的距离大于修剪距离，则高维空间中查询点到该节点中所有数据点之间的距离都大于修剪距离。证明设 Q表示查询点， Q 表示 Q 转换后低维空间中的点， -tree中某节点

13、中心C ， 半径为 R ， 设 P为该节点中的1个数据点，被转换为 P 。根据文献 1-2 中 PCA 的属性 1， 有如下等式成立：dist （P， Q ） dist （P， Q）（1）其中 dist （p， q ） 表示 p和 q两个数据点之间的距离， Dist （C1， Q） R1表示 Q到 -tree中该节点的距离， 所以有下式成立：dist （P， Q） dist （C1， Q） R1（2）由式（1） 和式（2） 得：dist （P， Q ） dist （C1， Q） R1（3）所以，dist （C1， Q） R1是高维空间中查询点到该节点中所有数据点之间距离的下限。如果dist （

14、C1， Q） R1比搜索半径大，那么查询点Q 到该节点中所有数据点的距离不可能比当前 kNN 更近（因为 dist （P， Q） 也一定大于搜索半径） ， 则可将该节点修剪掉。3非递归 KNN 查询算法算法 NR_DF_knn_Search及其子算法的符号说明：query-Point 为与数据集 R 中的数据点同时经过PCA 转换的查询点，root 为 -tree的根节点， computedChild 为 root （或 node ） 中计算了到 queryPoint 之间距离的孩子节点的集合，sortedNode 为computedChild 中按到 queryPoint 的距离由小到大排序

15、的孩子节点集合，point 为数据点，k为最近邻的数目， pruneDist 为 kNN的修剪距离， knnList 为装 kNN 候选的列表， kNN 在 knnList 中按到 queryPoint 的距离由小到大的排列。下面给出算法NR_DF_ knn_Search的 3个子算法 （算法 1至算法 3） 。算法 1 Compute_Child_Dist（计算查询点 queryPoint 到 root（或 node ） 中各孩子节点之间的距离）输入： queryPoint ， root （或 node ） ；输出： computedChild；begin（1）for rootor node

16、 中的每个孩子节点childidochildi.distance=P_dist （childi， queryPoint ， mchild.lev）；childi.id=i ； /childi.id 为孩子节点childi的序号（2）return child ；end定理 2 算法 1正确地计算了 queryPoint 到 root （或node ） 中各孩子节点之间的距离，能够返回 root （或node ） 中具有所计算距离和节点序号信息的所有孩子节点。时间复杂度为O （f mchild.lev）级。其中，f 是 -tree中节点的扇出， mchild.lev为根节点 root （或内部节点

17、 node ） 的孩子节点所在层的维数。证明 正确性：P_dist （ ） 首先使用 root （或 node ） 中的孩子节点所在层的维数计算queryPoint 到孩子节点childi中心的距离， 然后从该距离中减去孩子节点childi的半径作为 queryPoint与孩子节点 childi之间的距离。由定义2， 执行步骤（1） ， 为 root（或 node ） 中每个孩子节点计算queryPoint 与它们之间的距离，同时对该距离和孩子节点的序号进行了存储；执行步骤（2） ， 返回具有距离和序号信息的孩子节点。（可终止性） 算法中的 for 循环和 P_dist （ ）均可自动终止，故

18、算法是可终止的。（时间复杂度分析） 算法步骤 （1） 中 P_dist （ ） 为 O （mchild.lev）级， for 循环与 f 同级，故算法的时间复杂度为O （f mchild.lev）。证毕。算法 2 Sort_For_Child（为 computedChild 中的孩子节点按到 queryPoint 的距离排序 ）输入： computedChild；输出： sortedChild ；begin（1）变量 m=f ；（2）while 变量 L0 doL=0； / L 作为退出循环标志for 变量 i 从 1到 m1 doif computedChildi.distancecompu

19、tedChildi+1.distance thenswap （computedChildi， computedChildi+ 1）； /交换 computed-Childi和 computedChildi+1L=i ；/记录每次交换的位置m=L ； / m记录最后一个交换位置（3）return computedChild ；end.定理 3 算法 2为 computedChild 中的孩子节点按到query-Point 的距离正确地进行了由小到大的排序。时间复杂度为O （f2） 级。其中，f是 -tree中节点的扇出。证明由于进行比较的数据量f一般比较小 （100） ， 所以该算法采用改进的冒

20、泡排序算法，在原有的冒泡算法中增加了两个起标识作用的变量m和 L。变量 m用来标识最后一次发生交换的位置， 以此减少排序趟数。变量L 用来标识某趟排序后是否已经得到最终结果。（可终止性 ） 算法中的 for 和 while 循环可自动终止， 故算法是可终止的。（时间复杂度分析 ）算法步骤（2） 中 while 和 for 循环与 f 同级， 故算法的时间复杂度为O （f2） 。证毕。算法 3 Insert_knn_Candi （将数据点point 插入 kNN 列表knnList）输入： point， pruneDist， knnList；输出： knnList；begin（1）if knnL

21、ist.empty （ ） then刘艳， 郝忠孝：深度优先遍历 -tree的非递归 KNN 查询7名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 3 页 - - - - - - - - - Computer Engineering and Applications 计算机工程与应用2011， 47 （15）knnList .insert（1， point）；elseforknnList 中的每个candidateidoifpoint.distancek1 thenpru

22、neDist=candidatek.distance；ifknnList.size（） kthenknnList.erase（candidatek+1）；（2）return knnList ；end.定理 4 算法 3 正确地将 point 按序插入kNN 列表 knnList中， 且完成对 pruneDist 的更新，时间复杂度为O （k） 。其中，k为最近邻的数目。证明 正确性：执行步骤（1） ， 根据 knnList 中是否包含 kNN候选，以及包含kNN 候选的数目， 分情况将point 插入 knnList中： 当 knnList 为空时，直接调用 knnList 的 insert

23、（） 方法将 point插入 knnList 的最前端； 当 knnList 中包含kNN 候选时， 遍历knnList， 将 point 插入到 knnList 中首个比它到queryPoint 的距离大的 kNN 候选之前， 以保证 knnList 中 kNN 候选按到 query-Point 的距离由小到大排序，此时，如果 knnList 中包含 kNN 候选的数目大于k1， 则使用第 k个 kNN 候选到 queryPoint 的距离更新 pruneDist， 如果 knnList 中包含 kNN 候选的数目大于k，则将第 k+1 个 kNN 候选从 knnList 中删除。（可终止性

24、 ） 该算法中只有一个for 循环， 故可自动终止。（时间复杂度分析 ） 步骤 （1） 中的 for 循环与 k同级，故算法的时间复杂度为O （k） 。证毕。下面给出主算法NR_DF_knn_Search。算法 4 NR_DF_knn_Search （以非递归方式深度优先遍历 -tree的 kNN 查询算法 ）输入： queryPoint ， root， k；输出： queryPoint 在数据集 R中的 k最近邻；begin（1）Stack=NewStack（） ； knnList =NewKNN （ ）； pruneDist = ￥；（2）push （Stack， root） ；（3）wh

25、ileStack 1?dotopNode =pop（Stack ）；iftopNode.distancepruneDistor topNode 为 rootthen/ node.distance 表示 node 到 queryPoint 之间的距离iftopNode 为内部节点thencomputedChild=Compute_Child_Dist（queryPoint， topNode） ；sortedChild =Sort_For_Child （computedChild ） ；forsortedChild 中的孩子节点childi（下标 i 从 f到 1）doifchildi.dista

26、ncepruneDistthenpush （Stack， childi）；else/topNode 为叶子节点fortopNode 中的每个pointdopoint.distance =dist （point ， queryPoint ）；ifpoint.distancepruneDistthenknnList=Insert_knn_Candi （point， pruneDist ， knnList） ；（4）return knnList ；end.定理 5 算法 NR_DF_knn_Search采用非递归的方式对以root为根的 -tree正确地进行了深度优先的kNN查询， 时间复杂度为 O

27、(1+( fL 1f) /( f1)( fmchild.lev+ f2+f ) +fL (d + k)。其中， L 为 -tree的层数（ fL=N， N 为数据集 R的大小） ，为步骤 （3） 中第 1 个 if 语句和第 3个 if 语句的联合选择度， a 、 分别为步骤（3） 中第 3个 if 语句、 第 4个 if 语句的选择度， d 为数据点的维数。证明正确性： 执行步骤 （1）， 初始化栈Stack、 kNN 列表knnList 和修剪距离pruneDist； 执行步骤 （2 ）， 将 root 压入栈Stack。执行步骤 （3 ）， 将栈顶的节点弹出，设为 topNode， 根据

28、定理 1， 如果 topNode 到 queryPoint 之间的距离小于pruneDist，则根据 topNode的节点类型分两种情况进行处理：如果 topNode为内部节点， 首先调用算法Compute_Child_Dist 和 Sort_For_Child， 由定理 2、 定理 3， 可得到 computedChild 和 sortedChild，然后将 sortedChild 中到 queryPoint 的距离小于pruneDist 的孩子节点按由大到小的顺序依次入栈；如果 topNode 为叶子节点，则遍历topNode中的每个point， 使用 dist （） 计算 point 与

29、queryPoint 之间的距离， 根据定理 4， 将距离小于pruneDist 的point 插入 knnList， 如果栈 Stack非空，重复步骤（3） 中的操作，当栈 Stack为空时，该算法利用栈Stack对 -tree中所有节点按深度优先的顺序进行了遍历，并且对被遍历到的满足修剪条件的所有叶子节点进行了kNN 查询， 故该算法能够对 -tree完成非递归深度优先kNN 查询。（时间复杂度分析 ） 执行步骤（3 ） ， 算法 Compute_Child_Dist和 Sort_For_Child 的复杂度为O （fmchild.lev） 、 O （f2） ， 两个 for （ ）循环都

30、与 f同级。在步骤 （3） 中， -tree中的内部节点满足第3 个if语句且满足第 1个 if 语句的数目为 (fL- 1- f) /( f- 1) ， 故 -tree中包括 root 在内的内部节点执行步骤（3） 的时间复杂度为O(1+( fL - 1- f ) /( f - 1)( fmchild.lev+ f2+ f ) ； -tree中的叶子节点满足第 3个 if 语句且满足第 1个 if语句的数目为fL- 1， dist （ ）为 d 级， 算法 Insert_knn_Candi 的时间复杂度为O （k） ， 故 -tree中叶子节点执行步骤 （3 ） 的时间复杂度共为 O( fL

31、 (d + k) 。综上， 该算法总的时间复杂度为O(1+( fL - 1- f ) /( f - 1)( fmchild.lev+f2+ f )+ fL (d+ k) 。证毕。4实验设计与性能评价本章从时间和距离计算方面将算法NR_DF_knn_Search与算法 KNNSearch 进行了比较。实验在联想ThinkPad R400（2784A73）上进行， Windows7 Home Basic 操作系统， IntelCore2 Duo T6570 处理器、2 GB 内存、2 048 KB 二级缓存， 开发环境是 VC+6。真实数据从Corel data中取 50 000 个 64维数据，

32、最近邻的数目从2变化到 25。运行的结果如图1 所示， NR_DF_ knn_Search算法比 KNNSearch 算法的 CPU代价提高了 3.35.4倍， 数据点计算的数目提高了1.19.0倍。产生上述结果的原因在于：算法 NR_DF_ knn_Search利用堆栈，以非递归的方式对 -tree进行深度优先遍历，优先找到 -tree中距离查询点较近的叶子节点， 从而利用这些叶子节点中较优的 kNN 候选与查询点之间的距离快速缩小修剪距离，提高剪枝能力，有效地缩小搜索空间，减少计算量， 加快 kNN 查询效率。文献 1-2 中的 KNNSearch 算法使用的优先队列将其中的节点排序， 每次能够从队头取出距离查询点最近的内部节（下转 28页）8名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -