Integrating DCT and DWT for approximating cube streams

ABSTRACT

For time-relevant multi-dimensional data sets (MDS), users usually pose a huge amount of data due to the large dimensionality, and approximating query processing has emerged as a viable solution. Specifically, the cube streams handle MDSs in a continuous manner. Traditional cube approximation focuses on generating single snapshots rather than continuous ones. To address this issue, the application of generating snapshots for cube streams, called SCS, is investigated in this paper. Such an application collects data events for cube streams on-line and generates snapshots with limited resources in order to keep the approximated information in synopsis memory for further analysis. As compared to OLAP applications, the SCS ones are subject to much more resource constraints for both processing time and memory and cannot be dealt with by existing methods due to the limited resources. In this paper, the DAWA algorithm, standing for a hybrid algorithm of Dct for Data and discrete WAvelet transform, is proposed to approximate the cube streams. The DAWA algorithm combines the advantage of high compression rate from DWT and that of low memory cost from DCT. Consequently, DAWA costs much smaller working buffer and outperforms both DWT-based and DCT-based methods in execution efficiency. Also, it is shown that DAWA provides answers of good quality for SCS applications with a small working buffer and short execution time. The optimality of algorithm DAWA is theoretically proved and also empirically demonstrated by our experiments.

REFERENCES

• 1: Transactional Processing Performance Council. TPC Benchmark. Http://www.tpc.org.
• 2: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 3: C. S. Burrus, R. A. Gopinath, and H. Guo. Introduction to Wavelets and Wavelet Transforms. Prentice Hall, 1998.
• 4: E. Codd, S. Codd, and C. Salley. Providing OLAP(on-line analytical processing) to user-analysis: An IT mandate. Technical report, Arbor Software Corporation, 1993.
• 5: George Colliat, OLAP, relational, and multidimensional database systems, ACM SIGMOD Record, v.25 n.3, p.64-69, Sept. 1996 [doi>10.1145/234889.234901]
• 6: D. L. Donoho. De-noising by soft-thresholding. IEEE Transactions on Information Theory, 41(3):613--627, 1995.
• 7: D. Gabor. Theory of communication. Journal of the Institute of Electrical Engineers, 93(22):429, 1946.
• 8: Minos Garofalakis , Johannes Gehrke , Rajeev Rastogi, Querying and mining data streams: you only get one look a tutorial, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564794]
• 9: A. Haar. Theorie der orthogonalen funktionen-systeme. Mathematische Annalen, 69:331--371, 1910.
• 10: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 11: Björn Jawerth , Wim Sweldens, An overview of wavelet based multiresolution analyses, SIAM Review, v.36 n.3, p.377-412, Sept. 1994 [doi>10.1137/1036095]
• 12: Ju-Hong Lee , Deok-Hwan Kim , Chin-Wan Chung, Multi-dimensional selectivity estimation using compressed histogram information, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 13: Jae S. Lim, Two-dimensional signal and image processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 14: Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
• 15: S. S. Indexing OLAP data. Data Engineering Bulletin, 20(1):36--43, 1997.
• 16: 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
• 17: 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]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Management

Keywords:
OLAP, cube streams, data cubes, data streams