Dynamic shortest path monitoring in spatial networks | |
Shang, Shuo1,2; Chen, Lisi3; Wei, Zhe-4; Guo, Dan-Huai5; Wen, Ji-Rong4 | |
刊名 | Journal of computer science and technology |
2016-07-01 | |
卷号 | 31期号:4页码:637-648 |
关键词 | Shortest path Dynamic spatial network Spatial database Location-based service |
ISSN号 | 1000-9000 |
DOI | 10.1007/s11390-016-1653-3 |
通讯作者 | Guo, dan-huai(guodanhuai@cnic.cn) |
英文摘要 | With the increasing availability of real-time traffic information, dynamic spatial networks are pervasive nowadays and path planning in dynamic spatial networks becomes an important issue. in this light, we propose and investigate a novel problem of dynamically monitoring shortest paths in spatial networks (dspm query). when a traveler aims to a destination, his/her shortest path to the destination may change due to two reasons: 1) the travel costs of some edges have been updated and 2) the traveler deviates from the pre-planned path. our target is to accelerate the shortest path computing in dynamic spatial networks, and we believe that this study may be useful in many mobile applications, such as route planning and recommendation, car navigation and tracking, and location-based services in general. this problem is challenging due to two reasons: 1) how to maintain and reuse the existing computation results to accelerate the following computations, and 2) how to prune the search space effectively. to overcome these challenges, filter-and-refinement paradigm is adopted. we maintain an expansion tree and define a pair of upper and lower bounds to prune the search space. a series of optimization techniques are developed to accelerate the shortest path computing. the performance of the developed methods is studied in extensive experiments based on real spatial data. |
WOS关键词 | NEAREST-NEIGHBOR QUERIES ; IMAGE STEGANOGRAPHY ; TRAJECTORIES |
WOS研究方向 | Computer Science |
WOS类目 | Computer Science, Hardware & Architecture ; Computer Science, Software Engineering |
语种 | 英语 |
出版者 | SCIENCE PRESS |
WOS记录号 | WOS:000379087300002 |
内容类型 | 期刊论文 |
URI标识 | http://www.corc.org.cn/handle/1471x/2374170 |
专题 | 计算机网络信息中心 |
通讯作者 | Guo, Dan-Huai |
作者单位 | 1.State Key Lab Software Dev Environm, Beijing 100191, Peoples R China 2.China Univ Petr, Dept Comp Sci, Beijing 102249, Peoples R China 3.Nanyang Technol Univ, Sch Comp Engn, Singapore 639798, Singapore 4.Renmin Univ China, Beijing Key Lab Big Data Management & Anal Method, Beijing 100080, Peoples R China 5.Chinese Acad Sci, Comp Network Informat Ctr, Beijing 100190, Peoples R China |
推荐引用方式 GB/T 7714 | Shang, Shuo,Chen, Lisi,Wei, Zhe-,et al. Dynamic shortest path monitoring in spatial networks[J]. Journal of computer science and technology,2016,31(4):637-648. |
APA | Shang, Shuo,Chen, Lisi,Wei, Zhe-,Guo, Dan-Huai,&Wen, Ji-Rong.(2016).Dynamic shortest path monitoring in spatial networks.Journal of computer science and technology,31(4),637-648. |
MLA | Shang, Shuo,et al."Dynamic shortest path monitoring in spatial networks".Journal of computer science and technology 31.4(2016):637-648. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论