Managing Spatio-Temporal Data:Introduction and Background

Introduction and Background

Space and time are indispensable for many objects in the real world. Spatial databases represent, store and manipulate spatial data such as points, lines, areas, surfaces and hyper- volumes in multidimensional space. Most of these databases suffer from, what is commonly called, the “Curse of Dimensionality” [1]. Curse of dimensionality refers to a performance degradation of similarity queries with increasing dimensionality of these databases. One way to reduce this curse is to develop data structures for indexing such databases to answer similarity queries efficiently. Specialized data structures such as R-trees and its variants (Chapter 21), have been proposed for this purpose which have demonstrated multi-fold performance gains in access time on this data over sequential search.

Temporal databases, on the other hand, store time-variant data. Traditional spatial data structures can store only one ‘copy’ of the data, latest at the ‘present time’, while we frequently encounter applications where we need to store more than one copy of the data. While spatial data structures typically handle objects having spatial components and temporal data structures handle time-variant objects, research in Spatio-temporal data structures and data models have concentrated around storing moving points and moving objects, or objects with geometries changing over time.

Some examples of domains generating spatio-temporal data include but are not limited to the following: geographical information systems, urban planning systems, communication systems, multimedia systems and traffic planning systems. While the assemblage of spatio-temporal data is growing, the development of efficient data structures for storage and retrieval of these data types hasn’t kept pace with this increase. Research in spatio-temporal data abstraction is strewn but there are some important research results in this area that

have laid elemental foundation for development of novel structures for these data types. In this chapter we will present an assortment of key modeling strategies for Spatio-temporal data types.

In Spatio-temporal databases (STB), two concepts of times are usually considered: trans- action and valid time. According to [2], transaction time is the time during which a piece of data is recorded in a relation and may be retrieved. Valid time is a time during which a fact is true in the modeled reality. The valid time can be in the future or in the past.

There are two major directions [3] in the development of spatiotemporal data structures. The first direction is space-driven structures, which have indexing based upon the partitioning of the embedding multi-dimensional space into cells, independent of the distribution of the data in this space. An example of such a space-driven data structure is multiversion linear quadtree for storing spatio-temporal data. The other direction for storing spatiotemporal data is data-driven structures. These structures partition the set of the data objects, rather than the embedding space. Examples of data-driven structures include those based upon R-trees and its variants.

In this chapter, we will discuss both space-driven and data-driven data structures for storing spatio-temporal data. We will initiate our discussion with multiversion linear quad tree space driven data structure.