关于缓存技术的路网最短路径查询.pdf

第35卷第2期 东北大学学报( 自然科学版) V01．35．No．2 JoumalofNormeastem Feb．2O14 2叭4年2月 UniVersi够(NatIlralScience) doi：10．3969／j．issn．1005—3026．2014．02．011 基于缓存技术的路网最短路径查询 李晓华，王士猛，杨晓春，于 戈 (东北大学信息科学与工程学院，辽宁沈阳110819) 摘 要：分析了目前基于缓存进行路网上最短路径查询常用方法的不足，提出一种支持路网最短路径查 询的缓存管理方法．该方法在缓存有限的情况下，有效地选择那些不同但能满足更多查询请求的最短路径，将 其放入缓存．提出了缓存代价模型，并设计了缓存构造算法．最后采用真实数据集进行性能分析．实验测试显 示，本文提出的方法比现有方法具有更高的缓存命中率，平均执行效率优于现有的处理技术． 关键词：最短路径；缓存；代价模型；路网；命中率 311．13 中图分类号：TP 文献标志码：A 文章编号：1005—3026(2014)02—0199—05 Cache-basedShortestPath inRoadNetwork Query u‰D一厶蚴，黝』7、B鼬j一脚昭，M^够艇口。一如比忍，yU＆ ofInfo咖adon (School ScienceEngineering，Nor山eastemUIliversi哆，Shenyang aumor：LIⅪao_hua，E—mail：li)【iaohua@ise．neu．edu．cn) for on山e ofme ofme memods shortest Abstract：Based aIlalysisshortcoIIlingseXisting querying inroadnetwork anew metllodwas Whenme pam usingcache， cache．managing proposed． cache’ssizewas shortestwhichwere toanswerdif艳rent asmuch liIIlit．me pams expected queries as wereselected memetllodaJldstoredinthecache．Thecachebenefit possible effectivelyusing mOdelwas t11ecachestmcture The onrealdatasetaIldme pmposed．witll designed．experiments matthe canhitmore inthe resultsin demonsⅡate cache，which a11alVsis pmposedapproach pams tlle wimme average|1ighpe怕maIlcecomparedeXisting叩proaches． ratio sho