一种基于路网的连续最近邻查询算法.docx

一种基于路网的连续最近邻查询算法.docx一种基于路网的连续最近邻查询算法摘要:在路网中,连续最近邻(N)查询在基于位置的服务中尤为关键。现有的査询处理方法大多依赖于路网中查询对彖的分布密度,其他处理方法如UNICONS等改进了这些不足。然而在杳询对象密集分布的路网屮,存在无效计算最近邻(NearestNeighbor,NN)的问题。针对这个问题,本文提出并证明了非交叉点子路径屮的预计算方法,N查询算法。该算法利用分治法以交叉点为划分依据,将查询路径划分成了路径,然后对了路径中的结点进行NN查询,从而降低了NN查询的计算代价。通过实验,N查询屮的正确性和有效性,性能优势尤为明显。关键词:连续戢近邻査询;基于位置的服务;UNICONS;预计算方法;workWangHeng1,2Ying-YuanXiao1,21TianjinKeyLaboratory^putingandNovelSoftware7echnolog)\TianjinUniversityofTechnology^'Key^puterlesionandSystem(TianjinUniversityojTechnology).(RN),N)queryfrequentlyusedinLocation-BasedServices(LBS).Nqueriesarelargelyaffectedbythedensityofobjectsofinterest,etheseproblems,yettheremaybeover-,putationtheorybasedonnon-intersectionpath,Nquery,whichusesdivideandconquermethodtoqueryNNonsubpath,whereisdividedthequerypathintosubpathbasedonnon-intersectionpoints,,especiallytheresultiswellperformancewhentheintersectionpointssparselydistributed・N;LBS;UNICONS;putation;divideandconquermethod1引言随著移动计算、无线通讯、GIS(GeographicInformationSystem)s以及GPS空间定位、空间网络数据库(workDatabase,SNDB)等技术的迅速发展,基丁•位置的服务(Location-Based-Service,LBS)得到了广泛的应用。连续最近邻(ContinuousNearestNeighbor)查询山作为LBS中重要的查询类型,引起了国内外学者的关注。现有的杳询处理方法人多采用预计算的方法,该方法首先对路网进行处理(如空间区域划分、裁剪等),然后预先计算路网中结点的NN并进行存储,No与其他查询处理方法相比,该方法明显提高了查询的性能,并得到深入的研究。研究成果有:Feng等人⑵提出一种启发式的区域裁剪算法,通过该算法获得预计算的杳询区域(r-region),N查询问题。