Data-streams and histograms
Authors:
Open Access
- 6 July 2001
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 471-475
Abstract
Histograms have been used widely to capture data distribution, to represent the data by a small number of step functions. Dynamic programming algorithms which provide optimal construction of these histograms exist, albeit running in quadratic time and linear space. In this paper we provide linear time construction of 1 + &egr; approximation of optimal histograms, running in polylogarithmic space.Our results extend to the context of data-streams, and in fact generalize to give 1 + &egr; approximation of several problems in data-streams which require partitioning the index set into intervals. The only assumptions required are that the cost of an interval is monotonic under inclusion (larger interval has larger cost) and that the cost can be computed or approximated in small space. This exhibits a nice class of problems for which we can have near optimal data-stream algorithms.Keywords
This publication has 15 references indexed in Scilit:
- Optimal histograms for hierarchical range queries (extended abstract)2000
- Progressive vector transmission1999
- Join synopses for approximate query answering1999
- Random sampling techniques for space efficient online computation of order statistics of large datasets1999
- Approximate computation of multidimensional aggregates of sparse data using wavelets1999
- Data cube approximation and histograms via wavelets1998
- Wavelet-based histograms for selectivity estimation1998
- Random sampling for histogram construction1998
- Approximate medians and other quantiles in one pass and with limited memory1998
- Optimal histograms for limiting worst-case error propagation in the size of join resultsACM Transactions on Database Systems, 1993