Abstract
Existing work repeatedly addresses that the ubiquitous positioning devices will start to generate an unprecedented stream of time-stamped positions leading to storage and computation challenges. Hence the need for trajectory compression arises. The goal of this paper is to estimate the effect of compression in spatiotemporal querying; towards this goal, we present an analysis of this effect and provide a model to estimate it in terms of average false hits per query. Then, we propose a method to deal with the model’s calculation, by incorporating it in the execution of the compression algorithm. Our experimental study shows that this proposal introduces a small overhead in the execution of trajectory compression algorithms, and also verifies the results of the analysis, confirming that our model can be used to provide a good estimation of the effect of trajectory compression in spatiotemporal querying.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Almeida, V.T., Guting, R.H.: Indexing the Trajectories of Moving Objects in Networks. GeoInformatica 9(1), 33–60 (2005)
Brinkhoff, T.: A Framework for Generating Network-Based Moving Objects. Geoinformatica 6(2) (2002)
Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal Data Reduction with Deterministic Error Bounds. In: Proceedings of DIALM–POMC (2003)
Cheng, R., Kalashnikov, D., Prabhakar, S.: Querying Imprecise Data in Moving Object Environments. IEEE TKDE 16(9) (2004)
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, 112–122 (1973)
Frentzos, E.: Indexing Objects Moving on Fixed Networks. In: Proceedings of SSTD (2003)
Frentzos, E., Gratsias, K., Pelekis, N., Theodoridis, Y.: Algorithms for Nearest Neighbor Search on Moving Object Trajectories. Geoinformatica 11(2) (2007)
Hershberger, J., Snoeyink, J.: Speeding up the Douglas-Peucker line-simplification algorithm. In: Proceeedings of SDH (1992)
Meratnia, N., By, R.: Spatiotemporal Compression Techniques for Moving Point Objects. In: Proceedings of EDBT (2004)
Ni, J., Ravishankar, C.: Indexing Spatiotemporal Trajectories with Efficient Polynomial Approximation. IEEE TKDE 19(5) (2007)
Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving-object representations. In: Güting, R.H., Papadias, D., Lochovsky, F.H. (eds.) SSD 1999. LNCS, vol. 1651, Springer, Heidelberg (1999)
Pfoser, D., Jensen, C.S., Theodoridis, Y.: Novel Approaches to the Indexing of Moving Object Trajectories. In: Proceedings of VLDB (2000)
Potamias, M., Patroumpas, K., Sellis, T.: Sampling Trajectory Streams with Spatiotemporal Criteria. In: Proceedings of SSDBM (2006)
Potamias, M., Patroumpas, K., Sellis, T.: Amnesic online synopses for moving objects. In: Proceedings of CIKM (2006)
Theodoridis, Y. (ed.): The R-tree Portal (accessed 5 March, 2007), URL: www.rtreeportal.org
Trajcevski, G.: Probabilistic Range Queries in Moving Objects Databases with Uncertainty. In: Proceedings of MobiDE (2003)
Tao, Y., Papadias, D.: MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries. In: Proceedings of VLDB (2001)
Theodoridis, Y., Vazirgiannis, M., Sellis, T.: Spatio-temporal Indexing for Large Multimedia Applications. In: Proceedings of ICMCS (1996)
Trajcevski, G., Wolfson, O., Hinrichs, K., Chamberlain, S.: Managing uncertainty in moving objects databases. ACM TODS 29(3) (2004)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Frentzos, E., Theodoridis, Y. (2007). On the Effect of Trajectory Compression in Spatiotemporal Querying. In: Ioannidis, Y., Novikov, B., Rachev, B. (eds) Advances in Databases and Information Systems. ADBIS 2007. Lecture Notes in Computer Science, vol 4690. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75185-4_17
Download citation
DOI: https://doi.org/10.1007/978-3-540-75185-4_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-75184-7
Online ISBN: 978-3-540-75185-4
eBook Packages: Computer ScienceComputer Science (R0)