Journal
2019 IEEE 35TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2019)
Volume -, Issue -, Pages 1262-1273Publisher
IEEE
DOI: 10.1109/ICDE.2019.00115
Keywords
-
Categories
Funding
- 973 Program of China [2015CB358700]
- NSF of China [61632016, 61472198, 61521002, 61661166012]
- Huawei
- TAL education
Ask authors/readers for more resources
Many applications, e.g., Uber, collect large-scale trajectory data from moving vehicles on road network. Trajectory data analytics can benefit many real-world applications, such as route planning and transportation optimizations. Two core operations in trajectory data analytics are trajectory similarity search and join, and both of them rely on a trajectory similarity function to measure the similarity between two trajectories. However, existing similarity functions focus on trajectory points distance and neglect the fact the trajectories should be on road network. Obviously aligning trajectories on road network can remove the noise points introduced by system errors. Toward this goal, we define a road-network-aware trajectory similarity function to measure trajectory similarity. To support trajectory similarity search and join, we propose a filtering-refine framework. In the filtering step, we compute a signature of each trajectory such that if two trajectories are similar, they must share a common signature. We utilize the signatures to prune a huge number of dissimilar pairs. In the refine step, we design effective algorithms to verify the candidates that are not pruned in the filtering step. To support large-scale trajectories, we develop a system DISON for Distributed In-Memory Trajectory Similarity Search and Join on Road Network. DISON splits trajectories into disjoint partitions by considering load balance and locality, and designs effective global index to prune irrelevant partitions. Extensive experiments on real datasets showed that our method achieved high effectiveness, efficiency, and scalability and outperformed existing solutions significantly.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available