Spatio-Temporal Indexing Techniques

Spatio-Temporal Indexing Techniques

Michael Vassilakopoulos (University of Central Greece, Greece) and Antonio Corral (University of Almeria, Spain)
DOI: 10.4018/978-1-60566-242-8.ch029
OnDemand PDF Download:


Time and space are ubiquitous aspects of reality. Temporal and Spatial information appear together in many everyday activities, and many information systems of modern life should be able to handle such information. For example, information systems for traffic control, fleet management, environmental management, military applications, local and public administration, and academic institutions need to manage information with spatial characteristics that changes over time, or in other words, Spatio-temporal Information. The need for Spatio-temporal applications has been strengthened by recent developments in mobile telephony technology, mobile computing, positioning technology, and the evolution of the World Wide Web. Research and technology that aim at the development of Database Management Systems (DBMSs) that can handle Spatial, Temporal, and Spatio-temporal information have been developed over the last few decades. The embedding of spatio-temporal capabilities in DBMSs and GISs is a hot research area that will continue to attract researchers and the informatics industry in the years to come.
Chapter Preview


The term Spatial Data refers to multidimensional data, like points, line segments, regions, polygons, volumes, or other kinds of geometric entities, while the term Temporal Data refers to data varying in the course of time. Since in database applications the amount of data that should be maintained is too large for main memory, external memory (hard disk) is considered as a storage means. Specialized access methods are used to index disk pages and in most cases have the form of a tree. Numerous indexing techniques have been proposed for the maintenance of Spatial and Temporal Data. Two good sources of related information are the survey by Guenther and Gaede (1998) and the survey by Saltzberg and Tsotras (1999) for spatial and temporal access methods, respectively.

During last years, several researchers have focused on spatio-temporal data (spatial data that vary in the course of time) and the related indexing methods for answering spatio-temporal queries. A spatio-temporal query is a query that retrieves data according to a set of spatial and temporal relationships. For example, “find the vehicles that will be in a distance of less than 5km from a specified point within the next 5 minutes”. A number of recent short reviews that summarize such indexing techniques (especially, indexing of moving points) have already appeared in the literature. There are several ways for categorizing (several viewpoints, or classifications of) spatio-temporal access methods. In the rest of this section, we report on the approach followed by each of these reviews and on the material that the interested reader would find there.

In the book “Spatiotemporal Databases: the ChoroChronos Approach”, that was authored within the ChoroChronos project and edited by Sellis et al. (2003), chapter 6 is entitled “Access Methods and Query Processing Techniques” and reviews spatio-temporal access methods that have appeared up to 2001. The main classification followed in this chapter is between methods belonging in the R-tree family and methods belonging in the Quadtree family. The principle guiding the hierarchical decomposition of data distinguishes between these two indexing approaches. The two fundamental principles, or hierarchies are:

Key Terms in this Chapter

Spatio-Temporal Data Base Management System: A Data Base Management System that offers spatio-temporal data types and is able to store, index and query spatio-temporal data.

Movement in Transportation Networks: Movement (of a moving object) that is confined on a transportation network (such as rails, or roads).

Constrained (Unconstrained) Movement: Movement (of a moving object) that is (is not) confined according to a set of spatial restrictions.

Moving Object or Moving Point: A data element that is characterized by its position in space that varies in the course of time (this is a kind of spatio-temporal datum).

Spatio-Temporal Query: A set of conditions embedding spatial and temporal relationships that defines the set of spatio-temporal data to be retrieved.

Trajectory: The track followed by a moving object in the course of time (due to the change of its position).

Access Method or Indexing: A technique of organizing data that allows the efficient retrieval of data according to a set of search criteria. R-trees and Quadtrees are two well-known families of such techniques.

Spatio-Temporal Data: Multidimensional data, like points, line segments, regions, polygons, volumes, or other kinds of geometric entities that vary in the course of time.

Complete Chapter List

Search this Book: