《近邻查询算法的比较ppt课件》由会员分享，可在线阅读，更多相关《近邻查询算法的比较ppt课件（20页珍藏版）》请在金锄头文库上搜索。
1、芸“两种近邻查询舞法eJ燕山大学桉心内容提。概述。传统的K近邻查询算法。递增近邻查诲霍注。传统K近邻算法的简化。KiE邻算法向递增近邻算法的转化概述s传统的K近邻:K值是确定的,采j深度优先方式遍历R树。递增的近邻查询:K值不受约束,才最优优先方式遁历R树汞!传统的k近邹算法“算法从根节点开始,执行一深度优先遍历序列,遍布整棵树。“非叶子层,按照某度量标准将其子节点排序整理生成ABL(ActiveBranchList),并在ABL上执行裁剪策略1和z进行修剪,去除无用分支。“对于叶子层,计算查询点与对象的距离,并与当前Nearest比较,决定是否吏新Ne删髓t值“对ABL中元素迭代的执行算法直
2、到ABL为空。“在每次迭代过程中,算法选择列表中下一分支,递归地访问分支的孩子节点,并执行裁剪策略3。由最近邻搜索算法可以容易地得到K近邻的查询。它们的不同为:“一个分类的缓冲区需要,用来存储当前K个最近邻MBRs的袭剪是依据瑚冲区中最远最近邹的距离进行的逐增的最近F询递增最近邻算法用一个优先队列来记录遇到的结点、数据对象、对象矩形。相应INN算法描述(伪码如下页所示“1-2,队列的初始化“6-8,依接优先队列中顺序移除重复的对象实体“9,下一近邻被报告2,被报告过的对象不在加入队列,防止了对象被报告多次。INCNEAREsT(OueryObjechSpatialliuie)1Queie一Nz
3、WPRIogIYQmsUz02ENQUEQECQeue,Spoialdex.RootNode,0)3wlilenotISEMrY(Cueue)doBlemeg一DEQUEUECOuexe)IBlemerxisaspatialobjectthenWhileRlervet井玖Rsz(Oueue)doDELETEFIRsn(QOueleo)enddoReportEleredelseifBlenzii日alcaaodcthenforeachOljcclinleatncde5JeipentdeifDisTCQueryQBieci,Objec0DIsTCQOueryObjectElee)thenEamgu
4、z(Queue,DbjechDisz(QueryDbectObjecJ)endlfenddolse/Bjemmeyisanonleafnode吉foreachChIdnodeofnodeElementinSpoliaJuiexdoEhQugUg(Queue,CJldDrsT(QueryOAjectCJld)enddoendlfendido日日口启气厌史万吊口口万eoo、u一l恺N算法实例5寻找查询对象q的3近邻,其中空间对象为线性部分,存储在R-tree外部,分布如右图。算法必须计算q与线段和边界矩形的距离,距离在表中给出。算法从根结点入队列开始,接下来的步骤如下:1DequeueR0,enq
5、ueueR1andR2,Queue(Rl,0)(R2,0)心96HE5609UeUE3春4HEHE404王DequeueR2,tnqueue5andR6,Queue50).(84,0(,13)(6.44)车Dequele25,enqgueuecandi】(ie,theboumdingrectanglesofcandiQueue,0)(g4,1l)(R3,13)R6,44),(c5)5Dequeue口.Thedistanceofii21,whichislmgerthanhedistanceafF4,soengueueiQueue:(R4,11)(3,13),21)(6,44)(c53水6Dequ
6、eueRd,andenqueued,g,amda.Queusf(a23).(b,20),220.(a,3016,40(cl,53).(,747DequeleX3,enqueueaQoste(团23140012)(20).(,301(R6,4)(c,53)(Ig7&Dequeues.Thedistanceofais17,whichisnatlargerthanthedistancefb,soaisreportednearestneightorQueue(HJ;27),2D,(Ib,27).(a,30),(R6,24).(c,53)(g,74)9Dequeugk.Thedistanceofs17,
7、wtich识nollargerthan山edistanceofis0h乙eported8secondnearestneighberQueuett,21).(凶,20)(I41,30.(R6,4),(c,53).(Ig,74水0Dequeue士andreport尧8也训netrestneigtberSegDist|BRDia123原Db4827R|5c5753EL|0d5330R20e484513宇8674|巴E8740h1717R6|的1I符0Table1:DistancesofinesegmentsandboundingrectanglesfromthequerypointgintheR-treeofFigure1.由实例可得,对于INN算法,一旦找到最近邻,次近邻和三近邻是很容易得到的,无需太多额外工作。
