资源描述：
《Rav_tree_一种有效支持反向近似近邻查询的索引结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第37卷第1期计算机科学Vol.37No.12010年1月ComputerScienceJan2010Rav-tree:一种有效支持反向近似近邻查询的索引结构11,2李博涵郝忠孝1(哈尔滨理工大学计算机科学与技术学院哈尔滨150080)2(哈尔滨工业大学计算机科学与技术学院哈尔滨150001)摘要空间数据库的索引结构是实现有效数据查询的前提和基础。空间数据反向近似近邻查询是空间查询的一个新方向,它避免了精确查询中过多的距离计算,从而能够在效率与准确性上取得平衡。提出的Rav-tree不同于基于启发式规则
2、的索引结构,首先利用局部近似,然后根据Voronoicell区域和估计圆的方法实现近似近邻查询,并利用过滤结果和分域查询得到初步的候选集,最终通过反向近似近邻查询(RANNQuery)算法得到RANN集,并完整地给出基于Rav-tree的ANN查询算法和RANN查询算法。实验结果表明,Rav-tree对RANN等查询具有较好的查询效率和查全率。关键词索引结构,反向近似近邻,分域查询,区域估计中图法分类号TP311.13文献标识码ARav-tree:AnEfficientIndexStructurefor
3、ReverseApproximateNearestNeighborQuery11,2LIBo-hanHAOZhong-xiao(CollegeofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080,China)1(CollegeofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin150001,China)2Abstra
4、ctIndexstructureisthepreconditionandfoundationintheefficientdataquery.Thereverseapproximatenearestneighborqueryisanewissueintheareaofspatialquery.Thisapproachcanavoidmuchmetricdistancecomputationinexactquery,andacquireabettertradeoffbetweentheefficiencya
5、ndprecision.TheRav-treeisdifferentfromtheindexstructuresbasedontheheuristicrules.ItappliespartialVoronoicellapproximationwithestimatedcirclestofiltertheresultsofapproximatenearestneighborquery.ThefinalresultsetofRANNisreachedthroughthealgorithmsofANNquer
6、yandDivisionquerywithprimarycandidates.TheexperimentalresultsindicatethattheRav-treeisaneffectivein-dexstructureandhasbetterefficiencyandrecallforthequerysuchasRANNquery.KeywordsIndexstructure,Reverseapproximatenearestneighbor,Divisionquery,Regionestimat
7、ion近邻查询是空间数据库查询领域的一个重要问题,近年不借助任何启发式规则的索引结构,可以实现比较精确的近似来在GIS、Web查询引擎、设施定位、多媒体数据库等方面应近邻查询。但该索引结构利用圆型(球型)区域实现对Voronoi用广泛,也是查询的核心技术之一。目前空间数据查询的主[6]cell区域的估计方法存在局限性。该方法仅考虑了单独的[1][2,3][4]要分支有近邻、反向(k)近邻、k最近对查询等。这些Voronoicell的估计,不能有效地处理周围的Voronoicell的影查询主要是针对精确的
8、查询结果集,而实际的应用中有时可响,并且在高维的情况下近似扩展系数值不易确定。目前,近以利用查询的近似结果,以查询效率为第一目标,甚至可以忽邻查询中已有的关于反向近似查询解决方式难以解决存储近略一些结果。基于Z曲线的近似最近对[5]查询虽可以解决高邻记录代价较高且查询效率较低的问题,或者根本无法实现反维空间满足一定/相似0程度的最近对查询,但是降维过程中向近似近邻查询。反向近似近邻查询是对近邻查询的重要补采用不同曲线使查询性能差异较大,而且
