路网中基于Voronoi图的聚集最近邻查询技术研究.pdf

《路网中基于Voronoi图的聚集最近邻查询技术研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、路网中基于Voronoi图的聚集最近邻查询技术研究ResearchonVoronoi-basedAggregateNearestNeighborQueryinRoadNetworks导师孙未未副教授指导小组成员张亮教授荆一楠副教授谈子敬副教授张守志副教授摘要摘要移动计算、无线通信以及定位技术的快速发展使得对各种空间对象的存储和管理成为了现实需求。大量的应用领域(如地理信息系统、道路辅助与导航、急救服务、交通管制、与生活服务相关的查询、军事、移动电子商务等)均迫切需要有效地查询这些数据对象。然而，

2、空间数据固有的海量性和复杂性使得传统的数据库查询处理技术不能或不能有效地发挥作用，需要研究新的査询处理技术。因此，如何提供各种高效的空间对象查询处理技术是当前空间数据库领域的研究热点之一。空间数据库查询技术大都是基于欧式空间环境和道路网络（路网）环境。相比较而言，路网环境下的空间数据库查询会更有意义。因为它把空间对象限制在道路上，且查询点和空间对象只能按照路径移动。在路网环境下的查询与我们的生活更贴切。例如某个人找离他最近的加油站或餐馆。查询效率是空间数据库性能的重要指标，尽管有许多学者研究了路

3、网中的空间数据库查询，并取得了许多成果，但距离满足用户不断出现地、复杂而多样的查询需求还是有一定的差距，仍需要进一步深入研究。本文主要研究了路网环境下的聚集最近邻（AggregateNearestNeighbor,ANN)查询。当前对路网环境下ANN查询的研究[1]有两个缺陷：1.文献[1]性能最好的算法只适用于路网中边的权值与其长度成比例的情况。2.在有大量查询点的ANN查询中，算法的查询性能会很差。鉴于此，本文在路网Voronoi图(NetworkVoronoiDiagram，NVD)的基础

4、上，提出高效的算法解决ANN查询。本文提出的算法不仅解决了上述两个缺陷，而且在绝大部分情况下，算法性能要优于文献[1]中的算法。论文的主要贡献如下：1.本文使用NVD解决路网中的ANN查询，据我们所知，这是第一篇基于NVD解决ANN查询的文章；2.针对wot聚集函数和max聚集函数，分别设计了高效的剪枝策略；3.提出了VANN算法解决ANN查询、证明了算法的正确性、分析了时间复杂度。4.提出了AANN算法来解决大量查询点的ANN査询。5.提出了A:-VANN算法解决A-ANN查询，可以增量式地获

5、取下一个ANN。6.本文釆用真实数据集做了详细的实验，实验表明，本文提出的VANN算法和A:-VANN算法的性能在绝大部分下要优于文献[1]中的算法。关键字：道路网络，路网Voronoi图，聚集最近邻查询图文分类号:TP311.132TP391AbstractAbstractWiththerapiddevelopmentofMobileComputing,WirelessCommunicationsandPositioningTechnology,storingandmanagingavarie

6、tyofspaceobjectsbecometherealdemands.Alargenumberofapplicationareasareurgenttoeffectivelyquerythesedataobjects.However,themassandcomplexityofspatialdatamakesthattraditionaldatabasequeryprocessingtechniquescannotorcannoteffectivelyevaluatethesequeries

7、.Itneedbenewqueryprocessingtechniques.Therefore,howtoprovideavarietyofefficientspatialobjectqueryprocessingtechnologyisoneofthefocusesofcurrentresearchinthefieldofspatialdatabase.SpatialdatabasequeriesarebasedontheEuclideanspaceandroadnetwork.Usually

8、,queriesintheroadnetworkaremoremeaningful.Thisisbecauseitlimitstheobjectsontheroad，andquerypointsandspatialobjectscanonlymoveonthepath.Queriesinaroadnetworkaremoreappropriatetoourlives.Forexample,apersonwouldlikefindthenearestgasstationorrestaurantto