ÖÐÎÄ°æ English
É³ÌØ°¢²·¶ÅÀ­¹úÍõ¿Æ¼¼´óÑ§¼«ÏÞ¼ÆËãÖÐÐÄÑÐ¾¿Ô±ÉÌË¸Ñ§Êõ±¨¸æ

 ±¨¸æÊ±¼ä

Ê±¼ä£º10ÔÂ18ÈÕÉÏÎç08:40--09:30

µØµã£ºÇàµºÐ£ÇøN3Â¥402»áÒéÊÒ

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: