Fast, small-space algorithms for approximate histogram maintenance

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast, small-space algorithms for approximate histogram maintenance

Full text

Pdf (266 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 7A table of contents

Pages: 389 - 398

Year of Publication: 2002

ISBN:1-58113-495-9

Authors

Anna C. Gilbert	AT&T Labs---Research
Sudipto Guha	University of Pennsylvania
Piotr Indyk	MIT
Yannis Kotidis	AT&T Labs---Research
S. Muthukrishnan	AT&T Labs---Research
Martin J. Strauss	AT&T Labs---Research

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 77, Citation Count: 55

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.509966 What is a DOI?

ABSTRACT

(MATH) A vector A of length N is defined implicitly, via a stream of updates of the form "add 5 to A₃." We give a sketching algorithm, that constructs a small sketch from the stream of updates, and a reconstruction algorithm, that produces a B-bucket piecewise-constant representation (histogram) H for A from the sketch, such that ||A—H||&xie;(1+&egr;)||A—H_opt||, where the error ||A—H|| is either $\ell_1$ (absolute) or $\ell_2$ (root-mean-square) error. The time to process a single update, time to reconstruct the histogram, and size of the sketch are each bounded by poly(B,log(N),log||A,1/&egr;. Our result is obtained in two steps. First we obtain what we call a robust histogram approximation for A, a histogram such that adding a small number of buckets does not help improve the representation quality significantly. From the robust histogram, we cull a histogram of desired accruacy and B buckets in the second step. This technique also provides similar results for Haar wavelet representations, under $\ell_2$ error. Our results have applications in summarizing data distributions fast and succinctly even in distributed settings.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ashraf Aboulnaga , Surajit Chaudhuri, Self-tuning histograms: building histograms without looking at data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.181-192, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	2	Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
	3	J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
	4	Phillip B. Gibbons , Yossi Matias, Synopsis data structures for massive data sets, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.909-910, January 17-19, 1999, Baltimore, Maryland, United States
	5	Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast Incremental Maintenance of Approximate Histograms, Proceedings of the 23rd International Conference on Very Large Data Bases, p.466-475, August 25-29, 1997
	6	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
	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	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]
	10	P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
	11	H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
	12	Ju-Hong Lee , Deok-Hwan Kim , Chin-Wan Chung, Multi-dimensional selectivity estimation using compressed histogram information, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	13	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
	14	M. Naor, O. Reingold. Private communication, March, 1999.
	15	N. Nisan, Pseudorandom generators for space-bounded computations, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.204-212, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100242]
	16	V. Poosala. Histograms for selecitivty estimation. PhD Thesis, U. Wisconsin, Madison. 1997.
	17	Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]

CITED BY 55

	Phillip B. Gibbons , Yossi Matias , Viswanath Poosala, Fast incremental maintenance of approximate histograms, ACM Transactions on Database Systems (TODS), v.27 n.3, p.261-298, September 2002
	Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An information statistics approach to data stream and communication complexity, Journal of Computer and System Sciences, v.68 n.4, p.702-732, June 2004
	Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Moses Charikar , Kevin Chen , Martin Farach-Colton, Finding frequent items in data streams, Theoretical Computer Science, v.312 n.1, p.3-15, 26 January 2004
	Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Piotr Indyk, Algorithms for dynamic geometric problems over data streams, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003
	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
	Sreenivas Gollapudi , D. Sivakumar, Framework and algorithms for trend analysis in massive temporal data sets, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Matthew Roughan , Subhabrata Sen , Oliver Spatscheck , Nick Duffield, Class-of-service mapping for QoS: a statistical signature-based approach to IP traffic classification, Proceedings of the 4th ACM SIGCOMM conference on Internet measurement, October 25-27, 2004, Taormina, Sicily, Italy
	Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, One-Pass Wavelet Decompositions of Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.541-554, March 2003
	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
	Kathleen Fisher , Robert Gruber, PADS: a domain-specific language for processing ad hoc data, ACM SIGPLAN Notices, v.40 n.6, June 2005
	S. Muthukrishnan , Martin Strauss, Rangesum histograms, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	A. R. Calderbank , A. Gilbert , K. Levchenko , S. Muthukrishnan , M. Strauss, Improved range-summable random variable construction algorithms, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Camil Demetrescu , Irene Finocchi , Andrea Ribichini, Trading off space for passes in graph streaming problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.714-723, January 22-26, 2006, Miami, Florida
	Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, ACM Transactions on Database Systems (TODS), v.30 n.1, p.249-278, March 2005
	Minos Garofalakis , Amit Kumar, XML stream processing using tree-edit distance embeddings, ACM Transactions on Database Systems (TODS), v.30 n.1, p.279-332, March 2005
	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
	Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Graham Cormode , S. Muthukrishnan, An improved data stream summary: the count-min sketch and its applications, Journal of Algorithms, v.55 n.1, p.58-75, April 2005
	Graham Cormode , S. Muthukrishnan, What's hot and what's not: tracking most frequent items dynamically, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.296-306, June 09-11, 2003, San Diego, California
	Sumit Ganguly , Minos Garofalakis , Amit Kumar , Rajeev Rastogi, Join-distinct aggregate estimation over update streams, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
	Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, ACM Transactions on Database Systems (TODS), v.29 n.1, p.162-194, March 2004
	Graham Cormode , S. Muthukrishnan, What's new: finding significant differences in network data streams, IEEE/ACM Transactions on Networking (TON), v.13 n.6, p.1219-1232, December 2005
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Domain-Driven Data Synopses for Dynamic Quantiles, IEEE Transactions on Knowledge and Data Engineering, v.17 n.7, p.927-938, July 2005
	Kevin L. Chang , Ravi Kannan, The space complexity of pass-efficient algorithms for clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1157-1166, January 22-26, 2006, Miami, Florida
	Sudipto Guha , Andrew McGregor , Suresh Venkatasubramanian, Streaming and sublinear approximation of entropy and information distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.733-742, January 22-26, 2006, Miami, Florida
	Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, On graph problems in a semi-streaming model, Theoretical Computer Science, v.348 n.2, p.207-216, 8 December 2005
	Sudipto Guha , Nick Koudas , Kyuseok Shim, Approximation and streaming algorithms for histogram construction problems, ACM Transactions on Database Systems (TODS), v.31 n.1, p.396-438, March 2006
	A. C. Gilbert , S. Guha , P. Indyk , S. Muthukrishnan , M. Strauss, Near-optimal sparse fourier representations via sampling, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Mark Daly , Yitzhak Mandelbaum , David Walker , Mary Fernández , Kathleen Fisher , Robert Gruber , Xuan Zheng, PADS: an end-to-end system for processing ad hoc data, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA
	S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005
	Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation, Journal of the ACM (JACM), v.53 n.3, p.307-323, May 2006
	Wei Wang , Haifeng Jiang , Hongjun Lu , Jeffrey Xu Yu, Bloom histogram: path selectivity estimation for XML data with updates, Proceedings of the Thirtieth international conference on Very large data bases, p.240-251, August 31-September 03, 2004, Toronto, Canada
	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
	Utkarsh Srivastava , Jennifer Widom, Memory-limited execution of windowed stream joins, Proceedings of the Thirtieth international conference on Very large data bases, p.324-335, August 31-September 03, 2004, Toronto, Canada
	Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
	Anna C. Gilbert , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, How to summarize the universe: dynamic maintenance of quantiles, Proceedings of the 28th international conference on Very Large Data Bases, p.454-465, August 20-23, 2002, Hong Kong, China
	Flip Korn , S. Muthukrishnan , Divesh Srivastava, Reverse nearest neighbor aggregates over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.814-825, August 20-23, 2002, Hong Kong, China
	Bo Sheng , Chiu Chiang Tan , Qun Li , Weizhen Mao, Finding popular categories for RFID tags, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China
	Robert Schweller , Zhichun Li , Yan Chen , Yan Gao , Ashish Gupta , Yin Zhang , Peter A. Dinda , Ming-Yang Kao , Gokhan Memik, Reversible sketches: enabling monitoring and analysis over high-speed data streams, IEEE/ACM Transactions on Networking (TON), v.15 n.5, p.1059-1072, October 2007
	Sudipto Guha, On the space---time of optimal, approximate and streaming algorithms for synopsis construction problems, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.6, p.1509-1535, November 2008
	Piotr Indyk, Explicit constructions for compressed sensing of sparse signals, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.30-33, January 20-22, 2008, San Francisco, California
	Gautam Das , Dimitrios Gunopulos , Nick Koudas , Nikos Sarkas, Ad-hoc top-k query answering for data streams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Peter J. Haas , Fabian Hueske , Volker Markl, Detecting attribute dependencies from query feedback, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Hai Wang , Kenneth C. Sevcik, Histograms based on the minimum description length principle, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.3, p.419-442, May 2008
	Sudipto Guha , Hyoungmin Park , Kyuseok Shim, Wavelet synopsis for hierarchical range queries with workloads, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1079-1099, August 2008
	Panagiotis Karras , Nikos Mamoulis, Hierarchical synopses with optimal error guarantees, ACM Transactions on Database Systems (TODS), v.33 n.3, p.1-53, August 2008
	Yuval Ishai , Tal Malkin , Martin J. Strauss , Rebecca N. Wright, Private multiparty sampling and approximation of vector combinations, Theoretical Computer Science, v.410 n.18, p.1730-1745, April, 2009
	Panagiotis Karras, Multiplicative synopses for relative-error metrics, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Kevin L. Chang, Multiple pass streaming algorithms for learning mixtures of distributions in Rd, Theoretical Computer Science, v.410 n.19, p.1765-1780, April, 2009