Exploiting spatial autocorrelation to efficiently process correlation-based similarity queries

A spatial time series dataset is a collection of time series, each referencing a location in a common spatial framework. Correlation analysis is often used to identify pairs of potentially interacting elements from the cross product of two spatial time series datasets (the two datasets may be the same). However, the computational cost of correlation analysis is very high when the dimension of the time series and the number of locations in the spatial frameworks are large. In this paper, we use a spatial autocorrelation-based search tree structure to propose new processing strategies for correlation-based similarity range queries and similarity joins. We provide a preliminary evaluation of the proposed strategies using algebraic cost models and experimental studies with Earth science datasets.