Indexing continuously changing with mean-variance tree

Abstract

Constantly evolving data arise in various mobile applications such as location-based services and sensor networks. The problem of indexing the data for efficient query processing is of increasing importance. Due to the constant changing nature of the data, traditional indexes suffer from a high update overhead which leads to poor performance. In this paper, we propose a novel index structure, the MVTree, which is built based on the mean and variance of the data instead of the actual data values that are in constant flux. Since the mean and variance are relatively stable features compared to the actual values, the MVTree significantly reduces the index update cost. The distribution interval and probability distribution function of the data are not required to be known a priori. The mean and variance for each data item can be dynamically adjusted to match the observed fluctuation of the data. Experiments show that compared to traditional index schemes, the MVTree substantially improves index update performance while maintaining satisfactory query performance. Copyright 2005 ACM.