Counting large numbers of events in small registers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Counting large numbers of events in small registers

Full text

Pdf (250 KB)

Source

Communications of the ACM archive
Volume 21 , Issue 10 (October 1978) table of contents

Pages: 840 - 842

Year of Publication: 1978

ISSN:0001-0782

Author

Robert Morris

Bell Labs., Murray Hill, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 112, Citation Count: 14

Additional Information:

abstract 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/359619.359627 What is a DOI?

ABSTRACT

It is possible to use a small counter to keep approximate counts of large numbers. The resulting expected error can be rather precisely controlled. An example is given in which 8-bit counters (bytes) are used to keep track of as many as 130,000 events with a relative error which is substantially independent of the number n of events. This relative error can be expected to be 24 percent or less 95 percent of the time (i.e. &sgr; = n/8). The techniques could be used to advantage in multichannel counting hardware or software used for the monitoring of experiments or processes.

CITED BY 14

	Miklós Ajtai , T. S. Jayram , Ravi Kumar , D. Sivakumar, Approximate counting of inversions in a data stream, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, ACM SIGMOD Record, v.27 n.2, p.331-342, June 1998
	Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989
	Edith Cohen , Martin Strauss, Maintaining time-decaying stream aggregates, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.223-233, June 09-11, 2003, San Diego, California
	Edith Cohen , Martin J. Strauss, Maintaining time-decaying stream aggregates, Journal of Algorithms, v.59 n.1, p.19-36, April 2006
	Sudipto Guha , Andrew McGregor, Approximate quantiles and the order of the stream, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Andrej Cvetkovski, An algorithm for approximate counting using limited memory resources, ACM SIGMETRICS Performance Evaluation Review, v.35 n.1, June 2007
	Markus G. Kuhn, Probabilistic counting of large digital signature collections, Proceedings of the 9th conference on USENIX Security Symposium, p.6-6, August 14-17, 2000, Denver, Colorado
	D. Crippa , K. Simon , P. Trunz, Markov Processes Involving q-Stirling Numbers, Combinatorics, Probability and Computing, v.6 n.2, p.165-178, June 1997
	James Aspnes , Keren Censor, Approximate shared-memory counting despite a strong adversary, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.441-450, January 04-06, 2009, New York, New York
	Luca Becchetti , Carlos Castillo , Debora Donato , Ricardo Baeza-YATES , Stefano Leonardi, Link analysis for Web spam detection, ACM Transactions on the Web (TWEB), v.2 n.1, p.1-42, February 2008
	Bruno Ribeiro , Tao Ye , Don Towsley, A resource-minimalist flow size histogram estimator, Proceedings of the 8th ACM SIGCOMM conference on Internet measurement, October 20-22, 2008, Vouliagmeni, Greece
	Nan Hua , Bill Lin , Jun (Jim) Xu , Haiquan (Chuck) Zhao, BRICK: a novel exact active statistics counter architecture, Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, November 06-07, 2008, San Jose, California