时间：10月18日上午08:40--09:30

Topic: Trajectory Similarity Joinin Spatial Networks [PVLDB 2017]

Abstract:

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

With these applications in mind,we provide a purposeful definition of similarity. To enable efficient TS-Joinprocessing on large sets of trajectories, we develop search space pruningtechniques and take into account the parallel processing capabilities of modernprocessors. Specifically, we present a two-phase divide-and-conquer algorithm.For each trajectory, the algorithm first finds similar trajectories. Then itmerges the results to achieve a final result. The algorithm exploits an upperbound on the spatiotemporal similarity and a heuristic scheduling strategy forsearch space pruning. The algorithm's per-trajectory searches are independentof each other and can be performed in parallel, and the merging has constantcost.  An empirical study with real dataoffers insight in the performance of the algorithm and demonstrates that iscapable of outperforming a well-designed baseline algorithm by an order ofmagnitude.

Bio:

商烁，沙特阿卜杜拉国王科技大学（KAUST）极限计算中心研究员，博士生导师。中国GIS协会理论与方法委员会委员，中国计算机学会数据库专委会委员，2016年教育部-中国移动联合实验室评审专家组成员（新媒体组）。曾入选北京市科技新星计划、北京市优秀人才计划及中国石油大学（北京）青年拔尖人才计划。2008年本科毕业于北京大学，2012年博士毕业于澳大利亚昆士兰大学，2012-2013在丹麦奥尔堡大学任博士后/研究助理教授。2016年加入沙特阿卜杜拉国王科技大学，研究方向包括城市计算、时空数据库、社交媒体分析等。在相关领域发表论文40余篇，含CCF A类论文15篇，所发表SCI论文影响因子之和大于50SCI引用150余次，Google Scholar引用630余次。曾担任APWeb/WAIM 2017大会演示主席、ICDE 2013移动对象分会场主席，SIGMOD 2018ICDE 2018MDM2018CIKM 2017DASFAA 20142015 程序委员会委员，并担任VLDB JournalIEEE TKDEACM TISTACM TSASIEEE TITSGeoinformatica等数据管理和数据挖掘领域顶级期刊的评审专家。