SHIFT-SPLIT: I/O efficient maintenance of wavelet-transformed multidimensional data

ABSTRACT

The Discrete Wavelet Transform is a proven tool for a wide range of database applications. However, despite broad acceptance, some of its properties have not been fully explored and thus not exploited, particularly for two common forms of multidimensional decomposition. We introduce two novel operations for wavelet transformed data, termed SHIFT and SPLIT, based on the properties of wavelet trees, which work directly in the wavelet domain. We demonstrate their significance and usefulness by analytically proving six important results in four common data maintenance scenarios, i.e., transformation of massive datasets, appending data, approximation of data streams and partial data reconstruction, leading to significant I/O cost reduction in all cases. Furthermore, we show how these operations can be further improved in combination with the optimal coefficient-to-disk-block allocation strategy. Our exhaustive set of empirical experiments with real-world datasets verifies our claims.

REFERENCES

• 1: A. Bulut and A. K. Singh. SWAT: Hierarchical stream summarization in large networks. In Proceedings of ICDE, pages 303--314, 2003.
• 2: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 3: Antonios Deligiannakis , Nick Roussopoulos, Extended wavelets for multiple measures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872786]
• 4: Minos Garofalakis , Phillip B. Gibbons, Wavelet synopses with error guarantees, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564746]
• 5: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin Strauss, Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.79-88, September 11-14, 2001
• 6: Mehrdad Jahangiri , Cyrus Shahabi, ProDA: a suite of web-services for progressive data analysis, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066278]
• 7: Daniel Lemire, Wavelet-based relative prefix sum methods for range sum queries in data cubes, Proceedings of the 2002 conference of the Centre for Advanced Studies on Collaborative research, p.6, September 30-October 03, 2002, Toronto, Ontario, Canada
• 8: S. Papadimitriou, A. Brockwell, and C. Faloutsos. Awsom: Adaptive, hands-off stream mining. In Proceedings of VLDB, 2003.
• 9: Rolfe R. Schmidt , Cyrus Shahabi, ProPolyne: A Fast Wavelet-Based Algorithm for Progressive Evaluation of Polynomial Range-Sum Queries, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.664-681, March 25-27, 2002
• 10: C. Shahabi and R. Schmidt. Wavelet disk placement for efficient querying of large-multidimensional data sets. In Department of Computer Science Technical Reports. University Of Southern California, 2004.
• 11: Eric J. Stollnitz , Tony D. Derose , David H. Salesin, Wavelets for computer graphics: theory and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 12: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 13: Jeffrey Scott Vitter , Min Wang , Bala Iyer, Data cube approximation and histograms via wavelets, Proceedings of the seventh international conference on Information and knowledge management, p.96-104, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288645]
• 14: M. Widmann and C. Bretherton. 50 km resolution daily precipitation for the pacific northwest, 1949--94.
• 15: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, Using wavelet decomposition to support progressive and approximate range-sum queries over data cubes, Proceedings of the ninth international conference on Information and knowledge management, p.414-421, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354848]