Clustering Moving Objects for Spatio-temporal Selectivity Estimation

Abstract

Many spatio-temporal applications involve managing and querying moving objects. In such an environment, predic-tive spatio-temporal queries become an important query class to be processed to capture the nature of moving objects. In this paper, we investigated the problem of se-lectivity estimation for predictive spatio-temporal queries. We propose a novel histogram technique based on a clustering paradigm. To avoid expensive computation costs, we developed linear time heuristics to construct such a histogram. Our performance study indicated that the new techniques improve the accuracy of the existing techniques by one order of magnitude.