Dimensionality reduction for long duration and complex spatio-temporal queries

In this paper we present an approach to mine and query spatio-temporal data with the aim of finding interesting patterns and understanding the underlying data generating process. An important class of queries is based on the flock pattern. A flock is a large subset of objects moving along paths close to each other for a certain pre-defined time. One approach to process a "flock query" is to map spatio-temporal data into a high dimensional space and reduce the query into a sequence of standard range queries which can be presented using a spatial indexing structure. However, as is well known, the performance of spatial indexing structures drastically deteriorates in high dimensional space. In this paper we propose a preprocessing strategy which consists of using a random projection to reduce the dimensionality of the transformed space. Our experimental results show, for the first time, the possibility of breaking the curse of dimensionality in a spatio-temporal setting.