主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2022年专刊出版计划 微信服务介绍 最新一期:2021年第2期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
郝晋瑶,牛保宁,康家兴.大规模路网图下关键词覆盖最优路径查询优化.软件学报,2020,31(8):2543-2556
大规模路网图下关键词覆盖最优路径查询优化
Optimization of Keyword-aware Optimal Route Query on Large-scale Road Networks
投稿时间:2018-06-08  修订日期:2018-08-31
DOI:10.13328/j.cnki.jos.005808
中文关键词:  个性化旅游路线  关键词覆盖最优路径  大规模路网图  路网图划分  最小代价剪枝
英文关键词:personalized travel route  keyword-aware optimal route  large scale road network  road network partitioning  minimum cost pruning
基金项目:国家自然科学基金(61572345)
作者单位E-mail
郝晋瑶 太原理工大学 信息与计算机学院, 山西 晋中 030600  
牛保宁 太原理工大学 信息与计算机学院, 山西 晋中 030600 niubaoning@tyut.edu.cn 
康家兴 太原理工大学 信息与计算机学院, 山西 晋中 030600  
摘要点击次数: 383
全文下载次数: 356
中文摘要:
      游客倾向于采用个性化的旅游路线,规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询(KOR)就是用于规划这样的路线的一类查询,其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大,现有算法预处理所需内存开销急剧上升,由于内存不足,导致较大规模的路网不能处理;路径拓展搜索空间快速膨胀,应用场景可扩展性与查询实时性难以保证.针对这些问题,提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图,仅保存子图内路径和子图之间路径的信息,以减小预处理所需内存.在路径拓展阶段,综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化,以高效地搜索近似最优解.采用美国各地区的路网图,在16G内存环境下进行实验,突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明,KORL算法具有良好的可扩展性.
英文摘要:
      Visitors tend to choose personalized travel routes. Planning such a route requires a comprehensive consideration of the length and cost of the route, and the points of interest covered by the route. Keyword-aware optimal route query (KOR) is a typical query for this purpose. Processing a KOR consists of preprocessing and route expansion. With the scale of maps of road networks continues to expand, the overhead for preprocessing and the search space for route expansion increase rapidly. The scalability and the real-time responsiveness are hard to guarantee. To alleviate these pain points, an algorithm called keyword-aware optimal route query algorithm on large-scale road networks or KORL is proposed. In the preprocessing stage, KORL reduces memory requirements by partitioning the road network into subgraphs and stores only information about the routes inside and between subgraphs. In the route expansion stage, KORL combines four strategies, namely minimum cost pruning, approximately dominance pruning, global priority expansion, and keyword vertex expansion to efficiently search the approximate optimal solution. The road networks of various regions in the United States are used as experimental datasets and the experiments are run by the computer with 16 G memory. The limitation that existing algorithms can only handle the road network with the number of vertexes less than 25K is broken. Experiments show that KORL has sound scalability.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利