基于Grid网格划分的改进路网最短路径查询.pdf

《基于Grid网格划分的改进路网最短路径查询.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014年9月第9期小型微型计算机系统Vo1．35No．92014JournalofChineseComputerSystems基于Grid网格划分的改进路网最短路径查询李晓华，王士猛，杨晓春，于戈(东北大学信息科学与工程学院软件研究所，沈阳110819)E．mail：lixiaohua@ise．neu．edu．cn摘要：最短路径查询作为图数据库管理的一项重要课题在近些年来受到国内外学者的广泛关注·在现实应用中有利存进行路网上最短路径查询成为一个重要的研究问题，而现有方法在缓存有限的条件下均不能高效地响应用户查请求：针对上述问题本文提出了一种有效的用于支持路网最短路径查

2、询的缓存代价模型，设计了缓存构造算法，进而高效的选择那些不同且能满足更多查询请求的最短路径放入缓存．基于此模型，利用Grid对大图进行划分，提高了查询效率，节省了辅助的存储空间和查询处理代价．最后采用真实数据集进行性能分析，实验结果显示本文提出的方法更有效·关键词：路网；最短路径；缓存；代价模型；划分中图分类号：TP311文献标识码：A文章编-~：1000-1220《2014)09-1937一D6ImprovingShortestPathQueryinRoadNetworkBasedOilGridPartitionUXiao．hua．WANGShi—meng，YANGX

3、iao-chun，YUGe(InformationScienceandEngineering。NortheasternUniversity．Shenyang110819，China)Abstract：Inrecentyears，shortestpathquerywhichisaimportanttopicingraphdatabasemanagementhasreceivedlotsofattentionofresearchers．Also，inrealapplications，howtoqueryshortestpathefectivelyusingcacheisan

4、importanttopic．However，existingcachingtechniquesareineffectiveforshortestpathquerieswithlimitedcachingspace．Motivatedbythis1weproposeanefectivecac‘hingcostmodeltosupportshortestpathqueriesusingcache．Also。wedesignagreedyalgorithmforselectingthevarietyandbenefi·cialshortestpathstOfulfillca

5、che．Basedonthismodel。weemployamethodtopartitionroadnetworkusingGrid-whichCanim-proveeffectivenessofshortestqueries，saveextraancillaryspaceandprocessingcosts．ExperimentalresultsOilrealdatasethaveshowntheeffectivenessofourbeneficialmode1．Keywords：roadnetwork；shortestpath；cache；benefitmodel

6、；partition1引言图2(见下页)显示交通抽象网络模型，V，vJ代表地点，e(，)代表两个地点之间存在的一条边，边上的权值反映两近年来，随着基于位置的服务和GPS技术的不断发展与个地点之间的距离，从V。到。的最短路径是

7、，边上的权重表示相应路径的代价指通过该路径的时间或费用．因此，基于图的路网最短路径查询刮计算结果是十分重要的问题并有广泛的应用．1．1研究动机在交通网络中，人们想利用服务器获得出行的最短路径，图1表示用户提交两点最短路径查询请求给服务器，本地服务器用户并且通过全局服务器计算得到查询结果，然后把结果返回给图1web搜索用户．若本地服务器缓存中针对这个查询保留着查询结果，则Fig．1Websearch可以直接回答用户查询请求，节省了通信代价和计算时间，因此缓存能够在一定程度上减轻服务器工作代价，提高查询的基于有效缓存的最短路径查询方法常用的有