空间对象连续可视最近邻查询处理的研究

《空间对象连续可视最近邻查询处理的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学硕士学位论文摘要空间数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地发挥作用，需要研究新的查询处理技术。因此如何提供各种高效的空间与空间对象查询处理技术是当前空间数据库领域的研究热点之一。至今人们提出了利用不同空间索引结构进行空间数据库查询的多种类型，其中大多数都是基于R树索引结构的，例如最近邻查询、反最近邻查询、连续最近邻查询以及最近对查询等。但是这些查询算法都仅仅考虑了空间数据中只包含了查询对象这种情况，而不能适用于现实中存在障碍对象的空间数据库。本文结合常用的连续最近邻和可视最近邻查询类型，引入并提出了一种新颖的空间对象

2、查询类型及其处理方法：空间对象连续可视最近邻(ContinuousVisibleNearestNeighbor,CVNN)查询。在空间中查询对象和障碍对象两者并存的情况下，连续可视最近邻查询可以得到给定移动对象在其移动轨迹上的所有可视最近邻。这一查询算法可以应用在游戏中的AI部分以及领导的决策支持部分。另外，本文还探讨了空间对象CVNN查询的各种变体(如轨迹CVNN查询和受限CVNN查询等)。本文的主要贡献可概括如下：1)首先分析了问题本身的一些特性以及连续最近邻和连续可视最近邻的异同点，并提出了连续可视最近邻查询独特的性质和引理。2)算法中在遍历查询对

3、象R树结构时应用了剪枝启发式来减少中间结点的访问，而对障碍对象是否影响最终结果也提出方法进行快速判断来减少算法整体的运行时间。在整体结构上算法采用了逐步更新结果的方法，在保证结果准确性的同时在每一步都应用剪枝条件来缩小搜索空间。3)为了扩大算法在现实应用中的适应性，本文在基本算法基础上重新把算法结果中的可视最近邻个数从一个扩展到鼢1)个。同时考虑到空间对象数量级很大，并且问题本身特性可能导致大量的空间搜索，本文提出了查询算法的近似算法，以很小的代价得到近似结果。4)最后在连续可视最近邻查询的基础上进一步扩展出“轨迹的连续可视最近邻查询算法’’和“受限的连

4、续可视最近邻查询算法"，扩大了算法在不同环境中的应用。关键词：空间数据库，最近邻，连续最近邻，可视最近邻，连续可视最近邻，查询处理浙江大学硕士学位论文AbstractThegreatcapacityandcomplexityofspatialdatamakeconventionaldatabasequeryprocessingtechniquesnolongerwellsuited，andrequireexploitingnewqueryprocessingapproaches．Therefore，howtoprovideallkindsofeffici

5、entqueryprocessingtechniquesforspatialandspatiotemporalobjectsisoneofresearchhotspotsintheareaofspatialdatabasescurrently．Peoplehaveproposedvarioustypesofspatialdatabasequeryprocessingtechniqueswithdifferentspatialindexstructure，andmostofthemarebasedontheR．tree，suchasNearestNeigh

6、borQuery、ReverseNearestNeighborQuery、ContinuousNearestNeighborQueriesandClosestPairQuery．However,thesequeryalgorithmsareconsideredonlyforasituationinwhichspatialdataincludeonlythequeryobject，whichCannotbeappliedtotherealitysituationinwhichlargenumbersofobstaclesobjectexistinspace

7、．Thisdissertationanalysesthetwocommonquerytypes—ContinuousNearestNeighborQueryandVisibleNearestNeighborQuery,andproposedthetypeofContinuousVisibleNearestNeighbor(CVNN)Query,anoveltypeofspatialdatabasequery．Inthesituationthatbothqueryobjectandobstaclesobjectexistinspace，CVNNcarlob

8、tainallthevisiblenearestneighborsofamobi