资源描述：
《一种基于路网的连续最近邻查询算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一种基于路网的连续最近邻查询算法摘要：在路网中，连续最近邻（ContinuousNearestNeighbor，CNN）查询在基于位置的服务中尤为关键。现有的查询处理方法大多依赖于路网中查询对象的分布密度，其他处理方法如UNICONS等改进了这些不足。然而在查询对象密集分布的路网中，存在无效计算最近邻（NearestNeighbor，NN）的问题。针对这个问题，本文提出并证明了非交叉点子路径中的预计算方法，并基于该方法提出了CNN查询算法。该算法利用分治法以交叉点为划分依据，将查询路径划分成子路径，然后对子路径中的结点进行NN查
2、询，从而降低了NN查询的计算代价。通过实验，验证了本文提出的查询处理方法在CNN查询中的正确性和有效性，性能优势尤为明显。关键词：连续最近邻查询;基于位置的服务;UNICONS;预计算方法;分治算法AlgorithmforCNNQueryoverRoadNetworkWangHeng1,2Ying-YuanXiao1,21TianjinKeyLaboratoryofIntelligenceComputingandNovelSoftwareTechnology,TianjinUniversityofTechnology，30038
3、4,Tianjin2KeyLaboratoryofComputerVisionandSystem（TianjinUniversityofTechnology）,MinistryofEducation,300384,TianjinAbstractInRoadNetwork(RN),ContinuousNearestNeighbor(CNN)queryfrequentlyusedinLocation-BasedServices(LBS).ThemajorityoftheexistingworksonCNNqueriesarelarg
4、elyaffectedbythedensityofobjectsofinterest,otherssuchasUNICONSovercometheseproblems,yettheremaybeover-calculatingproblem.Inthispaper,weproposeandproofapre-computationtheorybasedonnon-intersectionpath,andthenpresentedanalgorithmforCNNquery,whichusesdivideandconquermet
5、hodtoqueryNNonsubpath,whereisdividedthequerypathintosubpathbasedonnon-intersectionpoints,andthentoreducethecomputationalcost.ExperimentalresultsshowthatourprocessingapproachintheCNNqueryiscorrectandeffective,especiallytheresultiswellperformancewhentheintersectionpoin
6、tssparselydistributed.KeywordsCNN;LBS;UNICONS;pre-computation;divideandconquermethod1引言随着移动计算、无线通讯、GIS（GeographicInformationSystem）、以及GPS空间定位、空间网络数据库（SpatialNetworkDatabase，SNDB）等技术的迅速发展，基于位置的服务（Location-Based-Service,LBS）得到了广泛的应用。连续最近邻（ContinuousNearestNeighbor）查询[1
7、]作为LBS中重要的查询类型，引起了国内外学者的关注。现有的查询处理方法大多采用预计算的方法，该方法首先对路网进行处理（如空间区域划分、裁剪等），然后预先计算路网中结点的NN并进行存储，最后处理查询路径上的CNN。与其他查询处理方法相比，该方法明显提高了查询的性能，并得到深入的研究。研究成果有：Feng等人[2]提出一种启发式的区域裁剪算法，通过该算法获得预计算的查询区域（r-region），然后计算查询路径上每个结点的NN。但该方法只能解决k=1的CNN查询问题。之后，Kolahdouzan等人[3]提出了基于VN3（Voro
8、noi-BasedNetworkNearestNeighbor）[4]的CNN查询处理算法UBA（UpperBoundAlgorithm）。但该方法需要进行大量的NN查询来查找划分点，并且查询NN的VN3方法，依赖于路网中查询对象的分布密度和k值的大小，计算代价
