Cheng Long
Raymond Chi-Wing Wong
Abstract
Trajectories of moving objects are collected in many applications. Raw trajectory data is typically very large, and has to be simplified before use. In this paper, we introduce the notion of direction-preserving trajectory simplification, and show both analytically and empirically that it can support a broader range of applications than traditional position-preserving trajectory simplification. We present a polynomial-time algorithm for optimal direction-preserving simplification, and another approximate algorithm with a quality guarantee. Extensive experimental evaluation with real trajectory data shows the benefit of the new techniques.
- S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matching vehicle tracking data. In VLDB'05, pages 853-864. Google Scholar
- S. Brakatsoulas, D. Pfoser, and N. Tryfona. Modeling, storing and mining moving object databases. In IDEAS'04, pages 68-77. Google Scholar
- H. Cao, O. Wolfson, and G. Trajcevski. Spatio-temporal data reduction with deterministic error bounds. The VLDB Journal, 15(3):211-228, 2006. Google Scholar
- M. Chen, M. Xu, and P. Fränti. A fast o(n) multiresolution polygonal approximation algorithm for gps trajectory simplification. IEEE Transactions on Image Processing, 21(5), 2012.Google Scholar
- Y. Chen, K. Jiang, Y. Zheng, C. Li, and N. Yu. Trajectory simplification method for location-based social networking services. In Proceedings of the 2009 International Workshop on Location Based Social Networks, pages 33-40. ACM, 2009. Google Scholar
- D. Douglas and T. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer, 11(2):112-122, 1973.Google Scholar
- F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In SIGMOD'07, pages 330-339. Google Scholar
- J. Gudmundsson, J. Katajainen, D. Merrick, C. Ong, and T. Wolle. Compressing spatio-temporal trajectories. Algorithms and Computation, pages 763-775, 2007. Google Scholar
- C.-C. Hung, W.-C. Peng, and W.-C. Lee. Clustering and aggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal, pages 1-24, 2011.Google Scholar
- G. Kellaris, N. Pelekis, and Y. Theodoridis. Map-matched trajectory compression. Journal of Systems and Software, 2013. Google Scholar
- A. Kolesnikov. Efficient online algorithms for the polygonal approximation of trajectory data. In MDM'11, pages 49-57. Google Scholar
- R. Lange, T. Farrell, F. Durr, and K. Rothermel. Remote real-time trajectory simplification. In PerComm'09, pages 1-10, 2009. Google Scholar
- J. G. Lee, J. Han, and X. Li. Trajectory outlier detection: A partition-and-detect framework. In ICDE'08, pages 140-149. Google Scholar
- J. G. Lee, J. Han, X. Li, and H. Gonzalez. Traclass: trajectory classification using hierarchical region-based and trajectory-based clustering. PVLDB'08, 1(1):1081-1094, 2008. Google Scholar
- J. G. Lee, J. Han, and K. Y. Whang. Trajectory clustering: a partition-and-group framework. In SIGMOD'07, pages 593-604. Google Scholar
- C. Long, R. C.-W.Wong, and H. Jagadish. Direction-preserving trajectory simplification (technical report). In http://www.cse.ust.hk/~raywong/paper/trajectory.pdf, 2013.Google Scholar
- N. Meratnia and R. de By. Spatiotemporal compression techniques for moving point objects. EDBT'04, pages 561-562.Google Scholar
- J. Muckell, J. H. Hwang, V. Patil, C. T. Lawson, F. Ping, and S. Ravi. Squish: an online approach for gps trajectory compression. In COM.Geo'11, pages 13:1-13:8. Google Scholar
- D. Patel, C. Sheng, W. Hsu, and M. L. Lee. Incorporating duration information for trajectory classification. In ICDE'12, pages 1132-1143. Google Scholar
- N. Pelekis, I. Kopanakis, G. Marketos, I. Ntoutsi, G. Andrienko, and Y. Theodoridis. Similarity search in trajectory databases. In TIME'07, pages 129-140. Google Scholar
- M. Potamias, K. Patroumpas, and T. Sellis. Sampling trajectory streams with spatiotemporal criteria. In SSDBM'06, pages 275-284. Google Scholar
- M. Singh, Q. Zhu, and H. Jagadish. Swst: A disk based index for sliding window spatio-temporal data. In ICDE'12, pages 342-353. Google Scholar
- J. Yuan, Y. Zheng, X. Xie, and G. Sun. Driving with knowledge from the physical world. In KDD'11, pages 316-324. Google Scholar
- Y. Zheng, X. Xie, and W. Y. Ma. Geolife: A collaborative social networking service among user, location and trajectory. IEEE Data Engineering Bulletin, 33(2):32-40, 2010.Google Scholar
Recommendations
Hierarchical topology-preserving simplification of terrains
We present an algorithm for simplifying terrain data that preserves topology. We use a decimation algorithm that simplifies the given data set using hierarchical clustering. Topology constraints, along with local error metrics, are used to ensure ...
Material-Discontinuity Preserving Progressive Mesh Using Vertex-Collapsing Simplification
Level Of Detail (LOD) modelling or mesh reduction has been found useful in interactive walkthrough applications. Progressive meshing techniques based on edge or triangle collapsing have been recognised useful in continuous LOD, progressive refinement, ...
Attribute preserving dataset simplification
VIS '01: Proceedings of the conference on Visualization '01This paper describes a novel application of feature preserving mesh simplification to the problem of managing large, multidimensional datasets during scientific visualization. To allow this, we view a scientific dataset as a triangulated mesh of data ...
Comments