Indexing continuously changing data 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.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Jeff Erickson, Indexing moving points (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.175-186, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335220]
• 2: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah, Change Tolerant Indexing for Constantly Evolving Data, Proceedings of the 21st International Conference on Data Engineering (ICDE'05), p.391-402, April 05-08, 2005 [doi>10.1109/ICDE.2005.32]
• 3: R. Cheng, Y. Xia, S. Prabhakar, R. Shah, and J. Vitter. Efficient indexing method for probablistic threshold queries over uncertain data. Proceedings of the 30th International Conference of Very Large Databases(VLDB), pages 876--887, 2004.
• 4: J. Kaufman, J. Myllymaki, and J. Jackson. IBM City Simulator 2.0. http://www.alphaworks.ibm.com/tech/citysimulator.
• 5: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 6: Dongseop Kwon , Sangjun Lee , Sukho Lee, Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree, Proceedings of the Third International Conference on Mobile Data Management, p.113-120, January 08-11, 2002
• 7: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 8: Y. Tao, D. Papadias, and J. Sun. The TPR*-Tree: An optimized spatio-temporal access method for predictive queries. Proceedings of the 29th International Conference on Very Large Databases(VLDB), pages 790--802, 2003.
• 9: J. Tayeb, O. Ulusoy, and O. Wolfson. A quadtree-based dynamic ttribute indexing method. The Computer Journal, pages 185--200, 1998.
• 10: University of California, Riverside. Spatial index library version 0.44.2b (java). http://www.cs.ucr.edu/marioh/spatialindex/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

Keywords:
data streaming, indexing, query and update processing