Dimensionality Reduction for Long Duration and Complex Spatio-Temporal Queries

From tracking of moose in Sweden, to movement of traf-fic in a large metropolis, spatio-temporal data is contin-uously being collected and made available in the public domain. This provides an opportunity to mine and query spatio-temporal data with the purpose of finding substan-tial patterns and understand 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. The standard approach to process a “flock query ” is to map spatio-temporal data into a high dimensional space and re-duce the query into a sequence of standard range queries which can be presented using a spatial indexing structure. However, as it is well known, the performance of spatial indexing structures drastically deteriorates in high dimen-sional space. In this paper we propose a preprocessing strategy which consists of using a random projection to reduce the dimen-sionality of the transformed space. We prove an ′′ − δ′′ probabilistic approximation which results from the projec-tion and present experimental results which show, for the first time, the possibility of breaking the curse of dimension-ality in a spatio-temporal setting. 1. Introduction and Relate