High-dimensional spatio-temporal indexing

There exist numerous indexing methods which handle either spatio-temporal or high-dimensional data well. How-
ever, those indexing methods which handle spatio-temporal data well have certain drawbacks when confronted
with high-dimensional data. As the most efficient spatio-temporal indexing methods are based on the R-tree and
its variants, they face the well known problems in high-dimensional space. Furthermore, most high-dimensional
indexing methods try to reduce the number of dimensions in the data being indexed and compress the information
given by all dimensions into few dimensions but are not able to store now - relative data. One of the most efficient
high-dimensional indexing methods, the Pyramid Technique, is able to handle high-dimensional point-data only.
Nonetheless, we take this technique and extend it such that it is able to handle spatio-temporal data as well. We
introduce a technique for querying in this structure with spatio-temporal queries. We compare our technique, the
Spatio-Temporal Pyramid Adapter (STPA), to the RST-tree for in-memory and on-disk applications. We show that
for high dimensions, the extra query-cost for reducing the dimensionality in the Pyramid Technique is clearly ex-
... mehr
ceeded by the rising query-cost in the RST-tree. Concluding, we address the main drawbacks and advantages of our
technique.