Title: Trajectory Similarity Join in Spatial Networks

时间:3月29日上午10:00

地点：东五楼210

Abstract:

The matching of similar pairs of objects, called similarity join, is fundamental functionality in data management. We consider the case of trajectory similarity join (TS-Join), where the objects are trajectories of vehicles moving in road networks. Thus, given two sets of trajectories and a threshold $\theta$, the TS-Join returns all pairs of trajectories from the two sets with similarity above $\theta$. This join targets applications such as trajectory near-duplicate detection, data cleaning, ridesharing recommendation, and traffic congestion prediction.

With these applications in mind, we provide a purposeful definition of similarity. To enable efficient TS-Join processing on large sets of trajectories, we develop search space pruning techniques and take into account the parallel processing capabilities of modern processors. Specifically, we present a two-phase divide-and-conquer algorithm. For each trajectory, the algorithm first finds similar trajectories. Then it merges the results to achieve a final result. The algorithm exploits an upper bound on the spatiotemporal similarity and a heuristic scheduling strategy for search space pruning. The algorithm's per-trajectory searches are independent of each other and can be performed in parallel, and the merging has constant cost. An empirical study with real data offers insight in the performance of the algorithm and demonstrates that is capable of outperforming a well-designed baseline algorithm by an order of magnitude.

简介:

商烁，沙特阿卜杜拉国王科技大学（KAUST）极限计算中心研究科学家。中国GIS协会理论与方法委员会委员，中国计算机学会数据库专委会委员，2016年教育部-中国移动联合实验室评审专家组成员。曾入选北京市科技新星计划和北京市优秀人才计划。2008年本科毕业于北京大学，2012年博士毕业于澳大利亚昆士兰大学。研究方向包括城市计算、时空数据库、社交媒体分析等。在相关领域发表论文50余篇，含CCF A类论文19篇，所发表SCI论文影响因子之和大于60，SCI引用200余次，Google Scholar引用780余次。获得WISE 2017最佳论文奖。担任WWW Journal客座编辑，IEEE Big Data Congress 2018 领域主席、APWeb/WAIM 2017演示主席、ICDE 2013移动对象分会场主席，VLDB 2019、SIGMOD 2018、ICDE 2018、CIKM 2018、2017程序委员会委员，并担任VLDB Journal、IEEE TKDE、ACM TIST、ACM TSAS、IEEE TITS 等数据管理和数据挖掘领域顶级期刊的评审专家。