微信里点“发现”，扫一下
二维码便可将本文分享至朋友圈
演讲摘要：The problem of identifying the k-shortest paths (KSPs for short) in a dynamic road network is essential to many location-based services. Road networks are dynamic in the sense that the weights of the edges in the corresponding graph constantly change over time, representing evolving traffic conditions. Very often such services have to process numerous KSP queries over large road networks at the same time, thus there is a pressing need to identify distributed solutions for this problem. However, most existing approaches are designed to identify KSPs on a static graph in a sequential manner (i.e., the shortest path is generated based on the shortest path), restricting their scalability and applicability in a distributed setting. We therefore propose KSP-DG, a distributed algorithm for identifying k-shortest paths in a dynamic graph. It is based on partitioning the entire graph into smaller subgraphs, and reduces the problem of determining KSPs into the computation of partial KSPs in relevant subgraphs, which can execute in parallel on a cluster of servers. A distributed two-level index called DTLP is developed to facilitate the efficient identification of relevant subgraphs. A salient feature of DTLP is that it indexes a set of virtual paths that are insensitive to varying traffic conditions, leading to very low maintenance cost in dynamic road networks. This is the first treatment of the problem of processing KSP queries over dynamic road networks. Extensive experiments conducted on real road networks confirm the superiority of our proposal over baseline methods.
讲者简介：于自强，博士、烟台大学计算机学院副教授、学科带头人。现为CCF数据库专委会和信息系统专委会执行委员，山东省人工智能学会理事。主要研究方向为大规模时空数据计算，相关成果发表在SIGMOD、VLDB、TKDE、EDBT、《软件学报》 等数据库和数据挖掘领域的国内外权威期刊和会议上。主持国家自然科学基金面上项目、青年项目、山东省重点研发计划等多项国家和省部级课题。获得2015年WAIM最佳论文奖、2016 ACM优博奖（济南）、2020 ACM学术新星奖（济南）。担任TKDE、JCST、EAAI、Information System、《软件学报》、《计算机研究与发展》等国内外学术期刊的审稿人以及AAAI、CIKM、DASFAA、APWeb-WAIM等国际知名会议的程序委员会委员。
第十九届CCF中国信息系统及应用大会
本期嘉宾
京公网安备11010802032778号