Efficient Index Structures for Spatio-Temporal Objects

authored by: Carsten Kleiner, Udo W. Lipeck
Abstract: We present a family of four tree-based access structures for indexing spatio-temporal objects. Our indexing methods support spatio-temporal, as well as purely spatial and purely temporal queries. In order to handle sets of extended spatio-temporal objects we propose to specialize generalized search trees by combining the advantages of the well-known spatial structures R∗-tree (Beckmann et al., 1990) and SS-tree (White and Jain, 1996). We consider size-based (R∗-tree like) and distance-based (SS-tree like) penalty metrics for insertions, and we view the temporal dimension either as a regular third or as a special dimension. We evaluate the four access methods on different real-life datasets and identify one of them to be the most efficient access structure for the case of general spatio-temporal data with known extents in every dimension. This method continues the R∗-tree split policy with penalty metric and insertion policy from the SS-tree and treats the temporal dimension as a special dimension.
Organisation(s): Institute of Practical Computer Science
Type: Contribution to book/anthology
Volume: 2000
Pages: 881-888
No. of pages: 8
Publication date: 2000
Publication status: Published
Peer reviewed: Yes
ASJC Scopus subject areas: Engineering(all)
Electronic version(s): https://doi.org/10.1109/DEXA.2000.875130 (Access: Closed)

BibTeX

@inbook{0badd816aa434eac9340e541034bb1e5,
title = "Efficient Index Structures for Spatio-Temporal Objects",
abstract = "We present a family of four tree-based access structures for indexing spatio-temporal objects. Our indexing methods support spatio-temporal, as well as purely spatial and purely temporal queries. In order to handle sets of extended spatio-temporal objects we propose to specialize generalized search trees by combining the advantages of the well-known spatial structures R∗-tree (Beckmann et al., 1990) and SS-tree (White and Jain, 1996). We consider size-based (R∗-tree like) and distance-based (SS-tree like) penalty metrics for insertions, and we view the temporal dimension either as a regular third or as a special dimension. We evaluate the four access methods on different real-life datasets and identify one of them to be the most efficient access structure for the case of general spatio-temporal data with known extents in every dimension. This method continues the R∗-tree split policy with penalty metric and insertion policy from the SS-tree and treats the temporal dimension as a special dimension.",
keywords = "Database languages, Database systems, Geography, Geometry, Indexing, Shape, Spatial databases, Tail, Testing, Transaction databases",
author = "Carsten Kleiner and Lipeck, {Udo W.}",
year = "2000",
doi = "10.1109/DEXA.2000.875130",
language = "English",
isbn = "0-7695-0680-1",
volume = "2000",
pages = "881--888",
booktitle = "Proceedings 11th International Workshop on Database and Expert Systems Applications",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
address = "United States",
}