Spatio-temporal data reduction with deterministic error bounds

ABSTRACT

A common way of storing spatio-temporalinformation about mobile devices is in the form of a 3D (2D geography + time) trajectory. We argue that when cellular phones and Personal Digital Assistants become location-aware, the size of the spatio-temporal information generated may prohibit efficient processing. We propose to adopt a technique studied in computer graphics, namely line-simplification, as an approximation technique to solve this problem. Line simplification uses a distance function in producing the trajectory approximation. We postulate the desiderata for such a distance: it should be sound, namely the error of the answers to spatio-temporal queries must be bounded. We analyze several distances, and prove that some are sound in this sense for some types of queries, while others are not. Interestingly, not a single distance analyzed proves to be sound for all the common spatio-temporal queries, and therefore multi-distance line-simplification is introduced and analyzed. Then we propose an aging mechanism which gradually shrinks the size of the trajectories as time progresses. Finally, we analyze experimentally the effectiveness of line-simplification in reducing the size of a trajectories database.

REFERENCES

• 1: Special issue on data reduction techniques. In IEEE Data Engineering, volume 20. 1998.
• 2: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 3: P.K. Agarwal and K. R. Varadarajan. Efficient algorithms for approximating polygonal chains. Discrete & Computational Geometry, 23:273--291, 2000.
• 4: Helmut Alt and Leonidas J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation A survey. Technical Report B 96-11, 1996.
• 5: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 6: W. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal of Computational Geometry Applications, 6:50--77, 1996.
• 7: Zhiyuan Chen , Johannes Gehrke , Flip Korn, Query optimization in compressed database systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.271-282, May 21-24, 2001, Santa Barbara, California, United States
• 8: D. Douglas and T. Peuker. Algorithms for the reduction of the number of points required to represent a digitised line or its caricature. The Canadian Cartographer, 10(2):112--122, 1973.
• 9: Luca Forlizzi , Ralf Hartmut Güting , Enrico Nardelli , Markus Schneider, A data model and data structures for moving objects databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.319-330, May 15-18, 2000, Dallas, Texas, United States
• 10: Minos Garofalakis , Phillip B. Gibbons, Wavelet synopses with error guarantees, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564746]
• 11: Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
• 12: G. Graefe and L. D. Shapiro. Data compression and database performance. In Proc. ACM/IEEE-CS Symp. on Applied Computing, 1991.
• 13: V. Hardle, G. Kerkyacharian, D. Picard, and A. Tsybakov. Wavelets, Approximation, and Statistical Applications. Springer, 1998.
• 14: John Hershberger , Jack Snoeyink, Speeding Up the Douglas-Peucker Line-Simplification Algorithm, University of British Columbia, Vancouver, BC, Canada, 1992
• 15: John D. Hobby, Polygonal approximations that minimize the number of inflections, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.93-102, January 25-27, 1993, Austin, Texas, United States
• 16: H. Imai and M. Iri. Polygonal approximations of a curve-formulations and algorithms. In Computational Morphology, pages 71--86. 1988.
• 17: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 18: R. McMaster. Automated line generalization. Cartographica, 24(2):74--111, 1987.
• 19: Dieter Pfoser , Christian S. Jensen, Capturing the Uncertainty of Moving-Object Representations, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.111-132, July 20-23, 1999
• 20: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 21: Evaggelia Pitoura , George Samaras, Locating Objects in Mobile Computing, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.571-592, July 2001 [doi>10.1109/69.940733]
• 22: Goce Trajcevski , Ouri Wolfson , Fengli Zhang , Sam Chamberlain, The Geometry of Uncertainty in Moving Objects Databases, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.233-250, March 25-27, 2002
• 23: Michalis Vazirgiannis , Ouri Wolfson, A Spatiotemporal Model and Language for Moving Objects on Road Networks, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.20-35, July 12-15, 2001
• 24: Dimitrios Gunopoulos, Discovering Similar Multidimensional Trajectories, Proceedings of the 18th International Conference on Data Engineering, p.673, February 26-March 01, 2002
• 25: Till Westmann , Donald Kossmann , Sven Helmer , Guido Moerkotte, The implementation and performance of compressed databases, ACM SIGMOD Record, v.29 n.3, p.55-67, Sept. 2000 [doi>10.1145/362084.362137]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Experimentation, Theory

Keywords:
line simplification, moving objects database