Wavelet synopsis for data streams: minimizing non-euclidean error

ABSTRACT

We consider the wavelet synopsis construction problem for data streams where given n numbers we wish to estimate the data by constructing a synopsis, whose size, say B is much smaller than n. The B numbers are chosen to minimize a suitable error between the original data and the estimate derived from the synopsis.Several good one-pass wavelet construction streaming algorithms minimizing the l2 error exist. For other error measures, the problem is less understood. We provide the first one-pass small space streaming algorithms with provable error guarantees (additive approximation) for minimizing a variety of non-Euclidean error measures including all weighted lp (including l∞) and relative error lp metrics.In several previous works solutions (for weighted l2, l∞ and maximum relative error) where the B synopsis coefficients are restricted to be wavelet coefficients of the data were proposed. This restriction yields suboptimal solutions on even fairly simple examples. Other lines of research, such as probabilistic synopsis, imposed restrictions on how the synopsis was arrived at. To the best of our knowledge this paper is the first paper to address the general problem, without any restriction on how the synopsis is arrived at, as well as provide the first streaming algorithms with guaranteed performance for these classes of error measures.

REFERENCES

• 1: 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
• 2: 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]
• 3: Ingrid Daubechies, Ten lectures on wavelets, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 4: 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]
• 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 , 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
• 8: 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]
• 9: 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
• 10: 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
• 11: S. Guha, C. Kim, and K. Shim. XWAVE: Optimal and approximate extended wavelets for streaming data. VLDB Conference, 2004.
• 12: 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
• 13: 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]
• 14: 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
• 15: 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
• 16: Y. Matias and D. Urieli. Manuscript, 2004.
• 17: Y. Matias and D. Urieli. Optimal workload-based wavelet synopses. Proc. of ICDT, 2005.
• 18: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000
• 19: 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
• 20: S. Muthukrishnan. Workload optimal wavelet synopsis. DIMACS TR, 2004.
• 21: G. Strang and T. Nguyen. Wavelets and Filter Banks. Wellesley-Cambridge Press, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
streaming algorithm, wavelet synopses