Spatio-temporal evolution: querying patterns of change in databases

ABSTRACT

This paper contributes a general approach to characterizing patterns of change in a spatio-temporal database.While there is a particular interest in modelling and querying how spatio-temporal entities evolve, the approach contributed by the paper is distinctive in being applicable without modification to aspatial entities as well. The paper uses the Tripod spatio-temporal model to describe and instantiate in detail the contributed approach. After briefly describing a typical application and providing basic knowledge about Tripod, the paper characterizes and classifies evolution queries and describes in detail how they are evaluated.

REFERENCES

• 1: Mikkel Agesen , Michael H. Böhlen , Lasse Poulsen , Kristian Torp, A Split Operator for Now-Relative Bitemporal Databases, Proceedings of the 17th International Conference on Data Engineering, p.41-50, April 02-06, 2001
• 2: R. G. G. Cattell , Douglas K. Barry , Mark Berler , Jeff Eastman , David Jordan , Craig Russell , Olaf Schadow , Torsten Stanienda , Fernando Velez, The object data standard: ODMG 3.0, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 3: Martin Erwig , Markus Schneider, Developments in Spatio-Temporal Query Languages, Proceedings of the 10th International Workshop on Database & Expert Systems Applications, p.441, September 01-03, 1999
• 4: Martin Erwig , Markus Schneider, Visual Specification of Spatio-Temporal Developments, Proceedings of the IEEE Symposium on Visual Languages, p.187, September 13-16, 1999
• 5: Martin Erwig , Markus Schneider, Spatio-Temporal Predicates, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.881-901, July 2002 [doi>10.1109/TKDE.2002.1019220 ]
• 6: Leonidas Fegaras , David Maier, Optimizing object queries using an effective calculus, ACM Transactions on Database Systems (TODS), v.25 n.4, p.457-516, Dec. 2000 [doi>10.1145/377674.377676]
• 7: Tony Griffiths , Alvaro A. A. Fernandes , Nassima Djafri , Norman W. Paton, A Query Calculus for Spatio-Temporal Object Databases, Proceedings of the Eighth International Symposium on Temporal Representation and Reasoning (TIME'01), p.101, June 14-16, 2001
• 8: Tony Griffiths , Alvaro A. A. Fernandes , Norman W. Paton , Keith T. Mason , Bo Huang , Michael F. Worboys, Tripod: A Comprehensive Model for Spatial and Aspatial Historical Objects, Proceedings of the 20th International Conference on Conceptual Modeling: Conceptual Modeling, p.84-102, November 27-30, 2001
• 9: Tony Griffiths , Alvaro A. A. Fernandes , Norman W. Paton , Bo Huang , Mike Worboys , Chris Johnson , Keith T. Mason , John Stell, Tripod: a comprehensive system for the management of spatial and aspatial historical objects, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512188]
• 10: S. Grumbach, P. Rigaux, M. Scholl, and L. Segoufin. The DEDALE Prototype. In G. Kuper, L. Libkin,and J. Paredaens, editors, Constraint Databases pages 365--382. Springer, 2000.
• 11: 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]
• 12: Ralf Hartmut Güting , Markus Schneider, Realm-based spatial data types: the ROSE algebra, The VLDB Journal — The International Journal on Very Large Data Bases, v.4 n.2, p.243-286, April 1995 [doi>10.1007/BF01237921]
• 13: L. Hattersley and R. Creeser.Longitudinal Study 1971--1991: History, Organization and Quality of Data Number 7 in ONS Series LS. The Stationery Office., London, 1995.
• 14: D. E. Knuth, J. H. Morris, and V. R. Pratt. Fast Pattern Matching in Strings.SIAM Journal of Computing 6(2):323--350, 1977.
• 15: Christine Parent , Stefano Spaccapietra , Esteban Zimányi, Spatio-temporal conceptual models: data structures + space + time, Proceedings of the 7th ACM international symposium on Advances in geographic information systems, p.26-33, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/320134.320142]
• 16: 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
• 17: Reza Sadri , Carlo Zaniolo , Amir M. Zarkesh , Jafar Adibi, A Sequential Pattern Query Language for Supporting Instant Data Mining for e-Services, Proceedings of the 27th International Conference on Very Large Data Bases, p.653-656, September 11-14, 2001
• 18: Erlend Tøssebro , Ralf Hartmut Güting, Creating Representations for Continuously Moving Regions from Observations, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.321-344, July 12-15, 2001
• 19: T. S. Yeh and B. de Cambray.Modeling Highly Variable Spatio-Temporal Data.In Proc. Australasian Database Conf.pages 221--230, 1995.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Algorithms

Keywords:
spatio-temporal databases, spatio-temporal query