Abstract
A spatial trajectory is a sequences of (x,y) points, each with a time stamp. This chapter discusses low-level preprocessing of trajectories. First, it discusses how to reduce the size of data required to store a trajectory, in order to save storage costs and reduce redundant data. The data reduction techniques can run in a batch mode after the data is collected or in an on-line mode as the data is collected. Part of this discussion consists of methods to measure the error introduced by the data reduction techniques. The second part of the chapter discusses methods for filtering spatial trajectories to reduce measurement noise and to estimate higher level properties of a trajectory like its speed and direction. The methods include mean and median filtering, the Kalman filter, and the particle filter.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Gelb, et al.: Applied Optimal Estimation. The MIT Press (1974)
Alvares, L., Bogorny, V., Kuijpers, B., de Macelo, J., Moelans, B., Palma, A.: Towards semantic trajectory knowledge discovery. Tech. rep., Hasselt University (2007)
Bellman, R.: On the Approximation of Curves by Line Segments Using Dynamic Programming. Communications of the ACM 4(6), 284 (1961)
Bogorny, V., Valiati, J., Alvares, L.: Semantic-based Pruning of Redundant and Uninteresting Frequent Geographic Patterns. Geoinformatica 14(2), 201–220 (2010)
Civilis, A., Jensen, C., Nenortaite, J., Pakalnis, S.: Efficient Tracking of Moving Objects with Precision Guarantee. In: IEEE International Conference on Mobile and Ubiquitus Systems: Networking and Services (MobiQuitous) (2004)
C.T. Lawson and S.S. Rvi and J.-H. Hwang: Compression and Mining of GPS Trace Data: New Techniques and Applications. Technical Report. Region II University Transportation Research Center
van Diggelen, F.: GNSS Accuracy: Lies, Damn Lies, and Statistics. GPS World (2007)
Doucet, A., Freitas, N., Gordon, N.: An Introduction to Sequential Monte Carlo Methods. In: Sequential Monte Carlo Methods in Practice., pp. 3–13. Springer: New York (2001)
Douglas, D., Peucker, T.: Algorithms for the Reduction of the Number of Points Required to Represent a Line or its Caricature. The Canadian Cartographer 10(2), 112–122 (1973)
Fox, D.: Adapting the Sample Size in Particle Filters Through KLD-Sampling. The International Journal of Robotics Research 22(12), 985–1003 (2003)
Giannotti, F., Nanni, M., Pedreschi, D., Renso, C., Trasarti, R.: Mining Mobility Behavior from Trajectory Data. In: International Conference on Computational Science and Engineering (CSE)., pp. 948–951 (2009)
Gordon, N.: Bayesian Methods for Tracking. Imperial College, University of London, London (1994)
Guting, R., M.H.Bohlen, Erwig, M., Jensen, C., Lorentzos, N., M, S., Vazirgiannis, M.: A Foundation for Representing and Querying Moving Objects. ACM Transaction on Database Systems (TODS) 25, 1–42 (2000)
G”uting, R., Schneider, M.: Moving Object Databases. Morgan Kaufmann, San Francisco, CA (2005)
Hershberger, J., Snoeyink, J.: Speeding up the Douglas-Peucker Line simplification Algorithm. In: International Symposium on Spatial Data Handling, pp. 134–143 (1992)
Hightower, J., Borriello, G.: Particle Filters for Location Estimation in Ubiquitous Computing: A Case Study. In: in 6th International Conference on Ubiquitous Computing., pp. 88–106 (2004)
Hung, C.C., Peng, W.C.: Model Driven Traffic Data Acquisition in Vehicle Sensor Networks. In: International Conference of Parallen Processing (ICPP)., pp. 424–432 (2011)
Jenks, G.: Lines, Computers, and Human Frailties. Annuals of the Association of American Geographers 71, 1–10 (1981)
Keogh, E., Chu, S., Hart, D., Pazzani, M.: An On-Line Algorithm for Segmenting Time Series. In: International Conference on Data Mining (ICDM), pp. 289–296 (2001)
Keogh, E., Pazzani, M.: An Enhanced Representation of Time Series which Allows Fast and Accurate Classification, Clustering and Relevance Feedback. In: International Conference of Knowledge Discovery and Data Mining (KDD)., pp. 239–241 (1998)
Keogh, E., Pazzani, M.: An On-Line Algorithm for Segmenting Time Series. In: Annual International ACM-SIGIR Conference on Research and Development in Information Retrieval (SIGIR). (1999)
Keogh, E., Smyth, P.: A Probabilistic Approach to Fast Pattern Matching in Time Series Databases. In: International Conference of Knowledge Discovery and Data Mining (KDD), pp. 24–30 (1997)
Kleinberg, J., Tardos, E.: Algorithm Design. Addison Wesley, Reading, MA (2005)
Maratnia, N., de By, R.: Spatio-Temporal Compression Techniques for Moving Point Objects. In: International Conference on Extending Database Technology (EDBT), pp. 765–782 (2004)
McMaster, R.: Statistical Analysis of Mathematical Measures of Linear Simplification. The American Cartographer 13, 103–116 (1986)
Murphy, K., Russell, S.: Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks. In: Sequential Monte Carlo Methods in Practice., pp. 499–515. Springer: New York (2001)
Potamias, M., Patroumpas, K., Sellis, T.: Sampling Trajectory Streams with Spatio-Temporal Criteria. In: International Conference on Scientific and Statistical Database Management (SSDBM), pp. 275–284 (2006)
Saltenis, S., Jensen, C., Leutenegger, S., Lopez, M.: Indexing the Positions of Continuously Moving Objects. In: ACM International Conference on Management of Data (SIGMOD), pp. 331–342 (2000)
Schmid, F., Richter, K.F., Laube, P.: Semantic Trajectory Compression. In: International Symposium on Advances in Spatial and Temporal Databases (SSTD). (2009)
Vitter, J.: Random sampling with a reservoir. ACM Transactions on Mathematical Software (TOMS) 11(1) (1985)
Wang, X., Tieu, K., Grimson, E.: Learning Semantic Scene Models by Trajectory Analysis. In: European Conference on Computer Vision (ECCV), pp. 110–123 (2006)
White, E.: Assessment of Line Generalization Algorithms. The American Cartographer 12, 17–27 (1985)
Wolfson, O., Sistla, P., Xu, B., Zhou, J., Chamberlain, S., Yesha, Y., Rishe, N.: Tracking Moving Objects Using Database Technology in DOMINO. In: The Fourth Workshop on Next Generation Information Technologies and Systems (NGITS), pp. 112–119 (1999)
Yan, Z.: Towards Semantic Trajectory Data Analysis: A Conceptual and Computational Approach. In: Internation Conference on Very Large Data Base (VLDB) PhD Workshop. (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Lee, WC., Krumm, J. (2011). Trajectory Preprocessing. In: Zheng, Y., Zhou, X. (eds) Computing with Spatial Trajectories. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-1629-6_1
Download citation
DOI: https://doi.org/10.1007/978-1-4614-1629-6_1
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-1628-9
Online ISBN: 978-1-4614-1629-6
eBook Packages: Computer ScienceComputer Science (R0)