Approximation algorithms for wavelet transform coding of data streams

ABSTRACT

Given a set of orthonormal basis functions {ψi} and a target function/vector f, the wavelet representation problem is to construct f as a combination of at most B basis vectors to minimize some normed distance between f and f. The problem is well understood if the error is the mean squared error: The largest (ignoring signs) B coefficients of the wavelet expansion should be retained. This strategy follows from the proof of optimality and is not a built-in constraint.The mean squared error, however, is not the optimization criterion in several scenarios. The above easy solution to the wavelet representation problem does not carry over to lp for p ≠ 2, and it turns out that restricting the solution to any subset of coefficients of size B or less is suboptimal compared to the best solution which can choose arbitrary real numbers. Further, all the previous literature on non-l2 errors only considered the Haar system.In this paper we provide the first approximation schemes for the unrestricted optimization problem. We provide a lower bounding technique based on a system of inequalities. We show that a modified greedy algorithm that retains the coefficients of expansion gives a O(log n) true (factor) approximation algorithm for a wide variety of compact wavelet systems, including Haar, Daubechies, Symmlets, Coiflets among others. This vindicates several scaling type algorithms which are used in practice. We subsequently augment the lower bound and give a FPTAS for the Haar system. The same ideas extend to a QPTAS for the more general class of compact wavelets mentioned above. We also consider adaptive quantization problems, which are generalizations of the B-term representations.

REFERENCES

• 1: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 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: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 4: R. DeVore. Nonlinear approximation. Acta Numerica, pages 1--99, 1998.
• 5: 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]
• 6: Minos Garofalakis , Phillip B. Gibbons, Probabilistic wavelet synopses, ACM Transactions on Database Systems (TODS), v.29 n.1, p.43-90, March 2004 [doi>10.1145/974750.974753]
• 7: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 8: Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Marin J. Strauss, Optimal and approximate computation of summary statistics for range aggregates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375598]
• 9: Anna C. Gilbert , S. Muthukrishnan , Martin J. Strauss, Approximation of functions over redundant dictionaries using coherence, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 10: 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
• 11: Sudipto Guha , Boulos Harb, Wavelet synopsis for data streams: minimizing non-euclidean error, Proceeding 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]
• 12: Sudipto Guha , Piotr Indyk , S. Muthukrishnan , Martin Strauss, Histogramming Data Streams with Fast Per-Item Processing, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.681-692, July 08-13, 2002
• 13: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 14: S. Guha , N. Mishra , R. Motwani , L. O'Callaghan, Clustering data streams, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.359, November 12-14, 2000
• 15: Y. E. Ioannidis. The history of histograms (abridged). Proc. of VLDB Conference, pages 19--30, 2003.
• 16: Charles E. Jacobs , Adam Finkelstein , David H. Salesin, Fast multiresolution image querying, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.277-286, September 1995 [doi>10.1145/218380.218454]
• 17: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 18: S. Mallat. A wavelet tour of signal processing. Academic Press, 1999.
• 19: Y. Matias and D. Urieli. Personal communication, 2004.
• 20: Y. Matias and D. Urieli. Optimal workload-based weighted wavelet synopses. Proc. of ICDT, pages 368--382, 2005.
• 21: 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
• 22: S. Muthukrishnan. Nonuniform sparse approximation using haar wavelet basis. DIMACS TR 2004-42, 2004.
• 23: 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

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Wavelets and fractals

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

General Terms:
Algorithms, Design, Theory