Unrestricted wavelet synopses under maximum error bound

ABSTRACT

Constructing Haar wavelet synopses under a given approximation error has many real world applications. In this paper, we take a novel approach towards constructing unrestricted Haar wavelet synopses under an error bound on uniform norm (L_∞). We provide two approximation algorithms which both have linear time complexity and a (log N)-approximation ratio. The space complexities of these two algorithms are O (log N) and O (N) respectively. These two algorithms have the advantage of being both simple in structure and naturally adaptable for stream data processing. Unlike traditional approaches for synopses construction that rely heavily on examining wavelet coefficients and their summations, the proposed construction methods solely depend on examining the original data and are extendable to other findings. Extensive experiments indicate that these techniques are highly practical and surpass related ones in both efficiency and effectiveness.

REFERENCES

• 1: KDD archive. http://kdd.ics.uci.edu.
• 2: 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]
• 3: Minos Garofalakis , Amit Kumar, Deterministic wavelet thresholding for maximum-error metrics, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055582]
• 4: Sudipto Guha, Space efficiency in synopsis construction algorithms, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 5: Sudipto Guha , Boulos Harb, Approximation algorithms for wavelet transform coding of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.698-707, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109633]
• 6: Sudipto Guha , Boulos Harb, Wavelet synopsis for data streams: minimizing non-euclidean error, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081884]
• 7: S. Guha and B. Harb. Approximation algorithms for wavelet transform coding of data streams. IEEE Transactions on Information Theory, 54(2):811--830, Feb. 2008.
• 8: Sudipto Guha , Kyuseok Shim , Jungchul Woo, REHIST: relative error histogram construction algorithms, Proceedings of the Thirtieth international conference on Very large data bases, p.300-311, August 31-September 03, 2004, Toronto, Canada
• 9: Panagiotis Karras , Nikos Mamoulis, One-pass wavelet synopses for maximum-error metrics, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 10: Panagiotis Karras , Dimitris Sacharidis , Nikos Mamoulis, Exploiting duality in summarization with deterministic guarantees, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281235]
• 11: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 12: S. Muthukrishnan. Subquadratic algorithms for workload-aware haar wavelet synopses. In FSTTCS, pages 285--296, 2005.
• 13: C. Pang, Q. Zhang, D. Hansen, and A. Maeder. Constructing unrestricted wavelet synopses under maximum error bound. http://e-hrc.net/pubs/papers/pdf/shiftWaveletRelACM-1.pdf. Technical Report (08/209), ICT CSIRO.
• 14: C. Pang, Q. Zhang, D. Hansen, and A. Maeder. Building data synopses within a known maximum error bound. In APWeb/WAIM2007, 2007.
• 15: Eric J. Stollnitz , Tony D. Derose , David H. Salesin, Wavelets for computer graphics: theory and applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 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: Q. Zhang, C. Pang, and D. Hansen. On multidimensional wavelet synopses for maximum error bounds. CSIRO Technical Report.