Fast, small-space algorithms for approximate histogram maintenance. (English) Zbl 1192.68962
Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 389-398, electronic only (2002).
For the entire collection see [Zbl 1074.68502].
MSC:
| 68W40 | Analysis of algorithms |
| 90B25 | Reliability, availability, maintenance, inspection in operations research |
References:
| [1] | A. Aboulnaga, S. Chaudhuri. Self-tuning Histograms: Building Histograms Without Looking at Data. SIGMOD 1999, 181-192. 10.1145/304182.304198 |
| [2] | N. Alon, Y. Matias, M. Szegedy. The Space Complexity of Approximating the Frequency Moments. JCSS 58(1): 137-147 (1999). 10.1006/jcss.1997.1545 · Zbl 0938.68153 |
| [3] | J. Feigenbaum, S. Kannan, M. Strauss, M. Viswanathan. An Approximate L1-Difference Algorithm for Massive Data Streams. FOCS 1999, 501-511. |
| [4] | P. B. Gibbons, Y. Matias. Synopsis Data Structures for Massive Data Sets SODA 1999, 909-910. · Zbl 0934.68045 |
| [5] | P. B. Gibbons, Y. Matias, V. Poosala. Fast Incremental Maintenance of Approximate Histograms. VLDB 1997, 466-475. |
| [6] | A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, M. Strauss. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. VLDB 2001, 79-88. |
| [7] | A. C. Gilbert, Y. Kotidis, S. Muthukrishnan, M. Strauss. QuickSAND: Quick Summary and Analysis of Network Data DIMACS Technical Report 2001-43. |
| [8] | S. Guha, N. Koudas. Approximating a Data Stream for Querying and Estimation: Algorithms and Performance Evaluation. ICDE 2002. |
| [9] | S. Guha, N. Koudas, K. Shim. Data-streams and histograms. STOC 2001, 471-475. 10.1145/380752.380841 · Zbl 1323.68567 |
| [10] | P. Indyk. Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. FOCS 2000, 189-197. |
| [11] | H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, T. Suel. Optimal Histograms with Quality Guarantees. VLDB 1998, 275-286. |
| [12] | J.-H. Lee, D.-H. Kim, C.-W. Chung. Multi-dimensional selectivity estimation using compressed histogram information. SIGMOD 1999, 205-214. 10.1145/304182.304200 |
| [13] | Y. Matias, J. S. Vitter, M. Wang. Dynamic Maintenance of Wavelet-Based Histograms. VLDB 2000, 101-110. |
| [14] | M. Naor, O. Reingold. Private communication, March, 1999. |
| [15] | N. Nisan Pseudorandom Generators for Space-Bounded Computation. STOC 1990, 204-212. 10.1145/100216.100242 |
| [16] | V. Poosala. Histograms for selecitivty estimation. PhD Thesis, U. Wisconsin, Madison. 1997. |
| [17] | N. Thaper, S. Guha, P. Indyk, N. Koudas. Dynamic Multidimensional Histograms. SIGMOD 2002. 10.1145/564691.564741 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
