Abstract
We can define as spatiotemporal any database that maintains objects with geometric properties that change over time, where usual geometric properties are the spatial position and spatial extent of an object in a specific d-dimensional space. The need to use spatiotemporal databases appears in a variety of applications such as intelligent transportation systems, cellular communications, and meteorology monitoring. This field of database research collaborates tightly with other research areas such as mobile telecommunications, and is harmonically integrated with other disciplines such as CAD/CAM, GIS, environmental science, and bioinformatics. Spatiotemporal databases stand at the crossroad of two other database research areas: spatial databases (Güting, 1994; Gaede & Gunther, 1998) and temporal databases (Salzberg & Tsotras, 1999). The efficient implementation of spatiotemporal databases needs new data models and query languages and novel access structures for storing and accessing information. In Güting, Bohlen, Erwig, Jensen, Lorentzos, Schneider, and Vazirgiannis (2000) a data model and a query language capable of handling such time-dependent geometries, including those changing continuously that describe moving objects, were proposed; the basic idea was to represent time-dependent geometries as attribute data types and to provide an abstract data type extension to the traditional database data models and query languages. In that paper, it was also discussed how various temporal and spatial models could possibly be extended to be spatiotemporal models.
TopThe problem of spatiotemporal indexing is considered in the standard external memory model. In this model each disk access transfers a contiguous block of B data items in a single input/output operation (I/O). The space complexity of a data structure is measured in terms of the amount of disk blocks it uses, while the time complexity of its various operations is expressed with the number of needed I/Os. In the sequel, we let N denote the number of stored objects and let n=N/B and k=K/B, where K denotes the size of the desired output.
Key Terms in this Chapter
Transaction Time Databases: Temporal databases, the supported time dimension of which is the transaction time dimension that is the time when a fact is stored in the database. Transaction time is consistent with the transaction serialization order.
Bitemporal Databases: Temporal databases that support both the valid and the transaction time.
Spatial Database: A database storing and handling objects that are equipped with spatial information (a position and an extent).
Data Structures: A collection of methods for storing and organizing sets of data in order to facilitate access to them. More formally data structures are concise implementations of abstract data types, where an abstract data type is a set of objects together with a collection of operations on the elements of the set.
Spatiotemporal Database: A database that maintains objects with geometric properties that change over time, where usual geometric properties are the spatial position and spatial extent of the object in a specific d-dimensional space.
Valid Time Databases: Temporal databases, the supported time dimension of which is the valid time dimension that is the time when a fact becomes valid (effective) with respect to the real world.
Secondary Memory Algorithms: Algorithms for handling information on secondary media, like hard disks, CD-ROMs, and so forth, and trying to minimize the number of accesses on them.
Database: A collection of interrelated persistent information stored and organized as a unit in order to serve a specific purpose and satisfy the demands of a set of users. A database can be considered to be an electronic filling system stored on mass-storage systems such as magnetic tape or disk. A database is one component of a database management system.