Efficient Index Structures for Spatio-Temporal Objects

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.