Indexing Problems In Spatiotemporal Databases
TR-CIS-2000-05
George N. Kollios

pdf version of this paper

Abstract:
Spatiotemporal databases manage spatial objects that change positions and/or extents over time. Examples include traffic surveillance data, climate and land cover data, demographic data and multimedia applications (animated movies). Since these databases are large in size, it is important to design efficient indexing schemes that can access and explore them.

We first study the problem of indexing spatial objects that have evolved in the past and the whole evolution of each object is known. We present methods to store these evolutions in external memory in order to answer efficiently range and nearest neighbor queries of the form: ``find the objects that were in area $S$ between time instants $t_i$ and $t_j$'', or ``find the $q$ nearest objects to a given position between time instants $t_i$ and $t_j$''. We reduce the problem to a partial-persistence one, that is, we use a 2-dimensional access method that is made partially persistent. We show that this approach leads to fast query time while still using space proportional to the total number of changes in the spatiotemporal evolution. What differentiates this problem from traditional temporal indexing approaches is that objects are allowed to move and/or change their extent continuously over time. We present novel methods to approximate such objects. We then, formulate the problem as an optimization problem for which we provide an efficient and effective solution for the case where objects move linearly. An extensive experimental study demonstrates the advantages of our approach over other straightforward solutions.

While the above study concentrates on historical queries (past states) of spatiotemporal data, of interest are also queries about the future behavior of such data. Here, we assume that the objects movement/change functions are known. We show how to index mobile objects in one and two dimensions using efficient dynamic external memory data structures. Our approach is to employ methods to store the motion function of each object and answer range and nearest neighbor queries using these methods.

Finally, we present a solution to the temporal membership problem which is likely to occur in temporal and spatiotemporal databases. Consider a set of objects that evolves over time by adding and deleting objects and these changes are timestamped. A temporal membership query asks whether a given object was in the set at a specific time instant. We present methods that use partially persistent hashing schemes to answer efficiently this type of queries. The proposed methods have linear space and perform better than other approaches in practice.