Title: Indexing continuously changing data with mean-variance tree

Authors: Yuni Xia, Reynold Cheng, Sunil Prabhakar, Shan Lei, Rahul Shah

Addresses: Department of Computer Science, Indiana University, Purdue University Indianapolis, USA. ' Department of Computer Science, University of Hong Kong, Hong Kong. ' Department of Computer Science, Purdue University, West Lafayette, USA. ' Department of Computer Science, Purdue University, West Lafayette, USA. ' Department Of Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA

Abstract: Traditional spatial indexes like R-tree usually assume the database is not updated frequently. In applications like location-based services and sensor networks, this assumption is no longer true since data updates can be numerous and frequent. As a result these indexes can suffer from a high update overhead, leading to poor performance. In this paper we propose a novel index structure, the Mean Variance Tree (MVTree), which is built based on the mean and variance of the data instead of the actual data values that can change continuously. Since the mean and variance are relatively stable features compared to the actual values, the MVTree significantly reduces the index update cost. The mean and the variance of the data item can be dynamically adjusted to match the observed fluctuation of the data. Our experiments show that the MVTree substantially improves index update performance while maintaining satisfactory query performance.

Keywords: indexing; query processing; update processing; data streaming; location-based services; sensor networks; data updates; mean variance tree; index updating; queries.

DOI: 10.1504/IJHPCN.2008.022302

International Journal of High Performance Computing and Networking, 2008 Vol.5 No.4, pp.263 - 272

Published online: 27 Dec 2008 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article