Signature-Based Trajectory Similarity Join

Emerging vehicular trajectory data have opened up opportunities to benefit many real-world applications, e.g., frequent trajectory based navigation systems, road planning, car pooling, etc. The similarity join is a key operation to enable such applications, which finds similar trajectory pairs from...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2017-04, Vol.29 (4), p.870-883
Main Authors: Ta, Na, Li, Guoliang, Xie, Yongqing, Li, Changqi, Hao, Shuang, Feng, Jianhua
Format: Article
Language:English
Subjects:
Algorithms
Alignment
Bidirectional control
Complexity theory
filtering-verification framework
Filtration
Indexes
Mapping
Navigation
Navigation systems
Public transportation
Roads
Sampling
signature-based method
Signatures
Similarity
similarity join
State of the art
Trajectories
Trajectory
trajectory similarity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Emerging vehicular trajectory data have opened up opportunities to benefit many real-world applications, e.g., frequent trajectory based navigation systems, road planning, car pooling, etc. The similarity join is a key operation to enable such applications, which finds similar trajectory pairs from two large collections of trajectories. Existing similarity metrics on trajectories rely on aligning sampling points of two trajectories. However, due to different sampling rates or different vehicular speeds, the sample points in similar trajectories may not be aligned. To address this problem, we propose a new bi-directional mapping similarity (BDS), which allows a sample point of a trajectory to align to the closest location (which may not be a sample point) on the other trajectory, and vice versa. Since it is expensive to enumerate every two trajectories and compute their similarity, we propose Strain-Join, a signature-based trajectory similarity join framework. Strain-Join first generates signatures for each trajectory such that if two trajectories do not share common signatures, they cannot be similar. In order to utilize this property to prune dissimilar pairs, we devise several techniques to generate high-quality signatures and propose an efficient filtering algorithm to prune dissimilar pairs. For the pairs not pruned by the filtering algorithm, we propose effective verification algorithms to verify whether they are similar. Experimental results on real datasets show that our algorithm outperforms state-of-the-art techniques in terms of both effectiveness and efficiency.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2017.2651821