Indexing continuously changing data with mean-variance tree. (29th December 2008)

• Record Type: Journal Article
• Authors: Xia, Yuni; Cheng, Reynold; Prabhakar, Sunil; Lei, Shan; , Rahul Shah
• Is Part Of: International journal of high performance computing and networking. Volume 5:Number 4(2008)
• Page Start: 263
• Page End: 272
• Publication Date: 2008-12-29
• Subjects: indexing -- query processing -- update processing -- data streaming -- location-based services -- sensor networks -- data updates -- mean variance tree -- index updating -- queries; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

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.