Article

Compressing spatio-temporal trajectories

Authors:

Joachim Gudmundsson,

Jyrki Katajainen,

Damian Merrick,

Thomas WolleAuthors Info & Claims

ISAAC'07: Proceedings of the 18th international conference on Algorithms and computation

Pages 763 - 775

Published: 17 December 2007 Publication History

Abstract

Trajectory data is becoming increasingly available and the size of the trajectories is getting larger. In this paper we study the problem of compressing spatio-temporal trajectories such that the most common queries can still be answered approximately after the compression step has taken place. In the process we develop an O(n log^k n)-time implementation of the Douglas-Peucker algorithm in the case when the polygonal path of n vertices given as input is allowed to self-intersect.

References

[1]

Agarwal, P.K., Varadarajan, K.R.: Efficient algorithms for approximating polygonal chains. Discrete & Computational Geometry 23(2), 273-291 (2000).

[2]

Aronov, B., Bose, P., Demaine, E.D., Gudmundsson, J., Iacono, J., Langerman, S., Smid, M.: Data structures for halfplane proximity queries and incremental Voronoi diagrams. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 80-92. Springer, Heidelberg (2006).

Digital Library

[3]

Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. In: Proceedings of the 2003 Joint Workshop on Foundations of Mobile Computing, pp. 33-42. ACM Press, New York (2003).

Digital Library

[4]

Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. The VLDB Journal 15(3), 211-228 (2006).

Digital Library

[5]

Chan, W.S., Chin, F.: Approximation of polygonal curves with minimum number of line segments. In: Ibaraki, T., Iwama, K., Yamashita, M., Inagaki, Y., Nishizeki, T. (eds.) ISAAC 1992. LNCS, vol. 650, pp. 378-387. Springer, Heidelberg (1992).

Digital Library

[6]

Douglas, D.H., Peucker, T.K.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer 10(2), 112-122 (1973).

[7]

Frank, A.U.: Socio-Economic Units: Their Life and Motion. In: Frank, A.U., Raper, J., Cheylan, J.P. (eds.) Life and motion of socio-economic units. GISDATA, vol. 8, pp. 21-34. Taylor & Francis, London (2001).

[8]

Gudmundsson, J., Laube, P., Wolle, T.: Encyclopedia of GIS. In: Movement Patterns in Spatio-Temporal Data, Springer (to appear).

[9]

Güting, R., Boehlen, M.H., Erwig, M., Jensen, C.S., Lorentzos, N., Nardelli, E., Schneider, M., Vazirgiannis, M.: A Foundation for representing and querying moving objects. ACM Transactions on Database Systems 25(1), 1-42 (2005).

Digital Library

[10]

Hershberger, J., Snoeyink, J.: Speeding up the Douglas-Peucker line-simplification algorithm. In: Proceedings of the 5th International Symposium on Spatial Data Handling, pp. 134-143. IGU Commission on GIS (1992).

[11]

Hershberger, J., Snoeyink, J.: Cartographic line simplification and polygon CSG formulæ in O(n log^* n) time. Computational Geometry--Theory and Applications 11(3-4), 175-185 (1998).

Digital Library

[12]

Hulbert, I.A.R.: GPS and its use in animal telemetry: The next five years. In: Sibbald, A.M., Gordon, I.J. (eds.) Proceedings of the Conference on Tracking Animals with GPS, Aberdeen, UK, pp. 51-60. Macaulay Insitute (2001).

[13]

Imai, H., Iri, M.: Computational-geometric methods for polygonal approximations of a curve. Computer Vision, Graphics, and Image Processing 36(1), 31-41 (1986).

Digital Library

[14]

Kwan, M.P.: Interactive geovisualization of activity-travel patterns using three dimensional geographical information systems: A methodological exploration with a large data set. Transportation Research Part C 8(1-6), 185-203 (2000).

[15]

Melkman, A., O'Rourke, J.: On polygonal chain approximation. In: Computational Morphology, pp. 87-95. North-Holland, Amsterdam (1988).

[16]

Overmars, M., van Leeuwen, J.: Maintenance of configurations in the plane. Journal of Computer and System Sciences 23(2), 166-204 (1981).

Cited By

Han WDeng ZChu JZhu JGao PShah T(2018)A parallel online trajectory compression approach for supporting big data workflowComputing10.1007/s00607-017-0563-8100:1(3-20)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s00607-017-0563-8
Macfarlane JXu B(2017)Temporal Sampling Constraints for GeoSpatial Path Reconstruction in a Transportation NetworkProceedings of the 10th ACM SIGSPATIAL Workshop on Computational Transportation Science10.1145/3151547.3151548(1-6)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3151547.3151548
Long CWong RJagadish H(2014)Trajectory simplificationProceedings of the VLDB Endowment10.14778/2735461.27354668:1(49-60)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.14778/2735461.2735466
Show More Cited By

Index Terms

Compressing spatio-temporal trajectories
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Compressing spatio-temporal trajectories

A trajectory is a sequence of locations, each associated with a timestamp, describing the movement of a point. Trajectory data is becoming increasingly available and the size of recorded trajectories is getting larger. In this paper we study the problem ...
Compressing Spatio-temporal Trajectories
Algorithms and Computation
Abstract
Trajectory data is becoming increasingly available and the size of the trajectories is getting larger. In this paper we study the problem of compressing spatio-temporal trajectories such that the most common queries can still be answered ...
Indexing Spatio-Temporal Trajectories with Efficient Polynomial Approximations

Complex queries on trajectory data are increasingly common in applications involving moving objects. MBR or grid-cell approximations on trajectories perform suboptimally since they do not capture the smoothness and lack of internal area of trajectories. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISAAC'07: Proceedings of the 18th international conference on Algorithms and computation

December 2007

929 pages

ISBN:3540771182

Editor:
Takeshi Tokuyama
Tohoku University, Graduate School of Information Sciences, Sendai, Japan

Sponsors

Support Center for Advanced Telecommunications Technology Research
Kayamori Foundation of Informational Science Advancement
Tohoku University: Tohoku University
The Telecommunications Advancement Foundation
New Horizons in Computing

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 17 December 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
3
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han WDeng ZChu JZhu JGao PShah T(2018)A parallel online trajectory compression approach for supporting big data workflowComputing10.1007/s00607-017-0563-8100:1(3-20)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s00607-017-0563-8
Macfarlane JXu B(2017)Temporal Sampling Constraints for GeoSpatial Path Reconstruction in a Transportation NetworkProceedings of the 10th ACM SIGSPATIAL Workshop on Computational Transportation Science10.1145/3151547.3151548(1-6)Online publication date: 7-Nov-2017
https://dl.acm.org/doi/10.1145/3151547.3151548
Long CWong RJagadish H(2014)Trajectory simplificationProceedings of the VLDB Endowment10.14778/2735461.27354668:1(49-60)Online publication date: 1-Sep-2014
https://dl.acm.org/doi/10.14778/2735461.2735466
Acevedo-Rodríguez JMaldonado-Bascón SLópez-Sastre RGil-Jiménez PFernández-Caballero A(2011)Clustering of trajectories in video surveillance using growing neural gasProceedings of the 4th international conference on Interplay between natural and artificial computation - Volume Part I10.5555/2009405.2009453(461-470)Online publication date: 30-May-2011
https://dl.acm.org/doi/10.5555/2009405.2009453
Buchin KBuchin Mvan Kreveld MLuo JWolfson OAgrawal DLu C(2009)Finding long and similar parts of trajectoriesProceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/1653771.1653813(296-305)Online publication date: 4-Nov-2009
https://dl.acm.org/doi/10.1145/1653771.1653813
Benkert MDjordjevic BGudmundsson JWolle T(2007)Finding popular placesProceedings of the 18th international conference on Algorithms and computation10.5555/1781574.1781660(776-787)Online publication date: 17-Dec-2007
https://dl.acm.org/doi/10.5555/1781574.1781660

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents