Representation of periodic moving objects in databases

ABSTRACT

In the real world, lots of objects with changing position can be found. Some of them repeat the same movement several times, called periodic movements. Examples include airplanes, trains, planets, and marine turtles. This paper describes a model for representing the periodic movements to be stored in a database system, exploiting the information about the repetitions. The model is generic enough to represent any kind of movement, not being restricted to objects with repetitions in their movement. We present algorithms to detect the repetitions and to convert to the periodic representation as well as the implementation of some operations on such representation. We show, in an experimental evaluation against the so-called flat representation, that the approach presented in this paper significantly improves the performance of query processing in a database system when dealing with objects with some periodic movement. We also show that, for the worst case where the objects do not follow any periodic movement at all, our approach still performs acceptably.

REFERENCES

• 1: Luca Anselma, Recursive Representation of Periodicity and Temporal Reasoning, Proceedings of the 11th International Symposium on Temporal Representation and Reasoning (TIME'04), p.52-59, July 01-03, 2004
• 2: Mengchu Cai , Dinesh Keshwani , Peter Z. Revesz, Parametric Rectangles: A Model for Querying and Animation of Spatiotemporal Databases, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.430-444, March 27-31, 2000
• 3: J. A. Cotelo Lema, L. Forlizzi, R. H. Güting, E. Nardelli, and M. Schneider. Algorithms for moving objects databases. The Computer Journal, 46(6):680--712, 2003.
• 4: Stefan Dieker , Ralf Hartmut Güting, Plug and Play with Query Algebras: SECONDO-A Generic DBMS Development Environment, Proceedings of the 2000 International Symposium on Database Engineering & Applications, p.380-392, September 18-20, 2000
• 5: Stefan Dieker , Ralf Hartmut Güting , Miguel Rodríguez Luaces, A Tool for Nesting and Clustering Large Objects, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.169, July 26-28, 2000 [doi>10.1109/SSDM.2000.869786]
• 6: 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
• 7: R. H. Güting, T. Behr, V. T. Almeida, Z. Ding, F. Hoffmann, and M. Spiekermann. secondo: An extensible DBMS architecture and prototype. Technical Report 313, Fernuniversität Hagen, Fachbereich Informatik, 2004.
• 8: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 9: Ralf Hartmut Guting , Victor Almeida , Dirk Ansorge , Thomas Behr , Zhiming Ding , Thomas Hose , Frank Hoffmann , Markus Spiekermann , Ulrich Telle, SECONDO: An Extensible DBMS Platform for Research Prototyping and Teaching, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.1115-1116, April 05-08, 2005 [doi>10.1109/ICDE.2005.129]
• 10: Kathleen Hornsby , Max J. Egenhofer , Patrick J. Hayes, Modeling Cyclic Change, Proceedings of the Workshops on Evolution and Change in Data Management, Reverse Engineering in Information Systems, and the World Wide Web and Conceptual Modeling, p.98-109, November 15-18, 1999
• 11: Peter Revesz , Mengchu Cai, Efficient Querying and Animation of Periodic Spatio-Temporal Databases, Annals of Mathematics and Artificial Intelligence, v.36 n.4, p.437-457, December 2002 [doi>10.1023/A:1016399308282]
• 12: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 13: Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez, Cost and Imprecision in Modeling the Position of Moving Objects, Proceedings of the Fourteenth International Conference on Data Engineering, p.588-596, February 23-27, 1998
• 14: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
data types, moving objects, periodic, spatio-temporal