Dynamic Shortest Path Monitoring in Spatial Networks

来源 :计算机科学技术学报(英文版) | 被引量 : 0次 | 上传用户:darklbueyz
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
With the increasing availability of real-time tra?c information, dynamic spatial networks are pervasive nowa-days 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 des-tination, 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.
其他文献
本文阐述近年快速康复外科在胃肠外科中的应用进展.认为快速康复外科理念应用于胃肠外科临床是安全有效的,但具体临床路径还需大量研究进一步规范化、专科化.
8月1日,江苏省沪宁、京沪、宁通等6条主要高速公路137辆巡逻车装上GPS指挥调度系统车载装置,江苏省交巡警GPS指挥调度系统正式启动。该系统的启动将实现对全省范围内交巡警
期刊
青壮年股骨颈骨折是高能量损伤的结果,在骨折线斜形或短螺旋形的基础上,常伴有股骨颈后侧皮质的粉碎.后侧皮质粉碎使骨折复位固定后很不稳定;破裂骨块的复位缺失,容易造成骨
Word embedding, which refers to low-dimensional dense vector representations of natural words, has demon-strated its power in many natural language processing t
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊
卵巢癌(ovarian cancer)是死亡率较高的妇科恶性肿瘤之一,初期常无症状,多数患者往往在晚期或出现转移后才发现,随着研究的深入,发现其发生、发展、诊治与DNA异常甲基化有密
硬膜穿破后头痛是脑膜穿破后的常见病发症.1898年Karl August Bier报道了第1例硬膜穿破后头疼. Bier认为这与硬脊膜穿破后脑脊液持续渗漏有关.本文介绍了PDPH的机制,危险因素
2018年7月10~11日,第十五届中日韩亚洲起重机安全论坛在中华文明发源地之一的河南省的长垣县隆重召开.来自日本与韩国的专家代表和国内各地的起重机施工企业、检测单位、租赁
期刊
门冬胰岛素30(BIAsp30)是最常用、临床研究最多的预混胰岛素(BHI)类似物剂型。本文就近年来该药临床应用的最新进展作一综述。1BIAsp30的药理学特点BIAsp30含有30%门冬胰岛素
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊