基于VAR树反向最近邻查询技术研究.pdf

第2o 期 计 算 机 技 术 与 发 展 Vo1．20 NO．6 2010 6 CI)ⅣⅡ)UTERTECHNOI．OGYANDDEVEI．OPMENT jun． 20l0 年 月 基于 VAR树的反向最近邻查询技术的研究 修建新 ，一，郝忠孝 ，3 (1．哈尔滨理工大学计算机科学与技术学院，黑龙江 哈尔滨 150080； 2．黑龙江东方学院计算机科学与电气工程学部，黑龙江 哈尔滨 150086； 3．哈尔滨工业大学 计算机科学与技术学院，黑龙江 哈尔滨 150001) 摘 要 ：在空问数据库中，反向最近邻查询技术是最重要的查询技术之一，它是在最近邻查询技术的基础上提 出的，如何 有效地实现反向最近邻查询一直是人们研究的热点。以往都是基于类似R树索引结构的查询 ，在高维的情况下，使查询 的速度急剧下降，形成 “维数灾难”。因此引用了一种新的索引结构—一VAR树 ，并对 VAR树进行了改进 ，引进了性能优 越的SR树，并给出了基于这种索引结构的最近邻和反最近邻查询的算法。经实验验证基于VAR树的反向最近邻查询算 法，在高维空间中的查询效率有了较大的提高。 关键词 ：SR一树 ；VAR树 ；最近邻 ；反向最近邻查询 中图分类号 ：TP311 文献标识码 ：A 文章编号 ：1673—629X(2010)06—0051—04 ResearchofReverseNearestNeighborQueryTechnology BasedonVAR _。。Tree XIUJian—xin-一．HAOZhong．xiao，。 (1．CollegeofComputerScience Technology，HarbinUniversityofScienceandTechnology，Harbin150080，China； 2．Dept．ofComputerScienceandElectricalEng．，HeilongiiangEastCo llege，Harbin150086，China； 3．GoIlgeeofComputerScienceandTechnology，HrabinInstituteofTcehnology，Harbin150001，China) Abstract：Inthespatialdatabase，thereversenearestneighborqueryisoneofthemostimportantqueries。whichisba：~ lonthene~st neighborquery，how toimplementeffectivelythereversenearestneighborquerieshavebeenahotissue．Inthepast，mostalebasedOn R—treeindexstmct~esimilartothequery，intheCSeofhigh—dimensionai，makingthesharpdeclineintherateofinquiries，a“dimen— siondisaster”．Proposeanew indexstructure— VAR treeand introducetheSR treeofhighpeHormanceafterimpmving theVAR— tree，andgivenearestneighborqueries andanti—nearestneighboralgorithmsbasedonthestructure．Experimentsshow thatthealgorithm ofthereversenearestneighborqueries basedonVAR～treeenhnacesthequeryefficiencyinhigh—dimen