A Uniform Representation for Trajectory Learning Tasks

ABSTRACT

Most trajectory data are collected with a constant sample rate (e.g. GPS data). However, the variance of velocities can be very large, which causes the non-uniformity of the sample points in trajectory dataset. That is, the trajectory dataset can be very sparse in some parts which cause most existing distance measures to get unexpected results. On the other hand, the dataset can be extremely dense in some other parts which results in unnecessarily high computational complexity. Due to the above phenomenon, choosing an appropriate sample rate becomes a difficult challenge. In order to address the dilemma, we propose a Step-Invariant Trajectory (SIT) representation that can provide a dynamic sample rate to represent any trajectories in a uniform way. The translation takes only linear time. We also propose an effective and scalable distance measure for SIT representation. We evaluate the effectiveness and efficiency of our representation along with its distance measure by performing multiple trajectory classification and clustering experiments. These results show that our distance measures on SIT representation is much more accurate and robust than other representations and distance measures on sparse trajectory datasets. Our approach can also achieve competitive accuracy compared with the state of the art model-based trajectory representations on dense datasets. However, the time required to translate the data to our representation is 2 orders of magnitude faster, on average, than translate to other model-based representations. Furthermore, our representation can also serve as a preprocessing step to provide high quality input to all trajectory learning methods.

References

1. D. Comaniciu and P. Meer. 2002. Mean shift: a robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence 24, 5 (May 2002), 603--619.
2. C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. 1994. Fast Subsequence Matching in Time-series Databases (SIGMOD). ACM, 419--429.
3. W. Hu, X. Li, G. Tian, S. Maybank, and Z. Zhang. 2013. An Incremental DPMM-Based Method for Trajectory Clustering, Modeling, and Retrieval (PAMI), Vol. 35. 1051--1065.
4. W. Lin, Y. Zhou, H. Xu, J. Yan, M. Xu, J. Wu, and Z. Liu. 2017. A Tube-and-Droplet-Based Approach for Representing and Analyzing Motion Trajectories (PAMI), Vol. 39. 1489--1503.
5. B. T. Morris and M. M. Trivedi. 2011. Trajectory Learning for Activity Understanding: Unsupervised, Multilevel, and Long-Term Adaptive Approach (PAMI), Vol. 33. 2287--2301.
6. S. Ranu, Deepak P, A. D. Telang, P. Deshpande, and S. Raghavan. 2015. Indexing and matching trajectories under inconsistent sampling rates (ICDE). 999--1010.
7. H. Wang, H. Su, K. Zheng, S. Sadiq, and X. Zhou. 2013. An Effectiveness Study on Trajectory Similarity Measures (ADC). Darlinghurst, Australia, Australia, 13--22.
8. W. Wang and M. ffi. Carreira-Perpin. 2010. Manifold blurring mean shift algorithms for manifold denoising. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. 1759--1766.
9. H. Xu, Y. Zhou, W. Lin, and H. Zha. 2015. Unsupervised Trajectory Clustering via Adaptive Multi-Kernel-based Shrinkage (ICCV).

Index Terms

• Information systems

  • Data management systems

    • Information integration

      • Data cleaning

  • Information systems applications

    • Data mining