article

Free access

Counting large numbers of events in small registers

Author:

Robert MorrisAuthors Info & Claims

Communications of the ACM, Volume 21, Issue 10

Pages 840 - 842

https://doi.org/10.1145/359619.359627

Published: 01 October 1978 Publication History

PDF eReader

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. σ = 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

View all

Sateesan AVliegen JScherrer SHsiao HPerrig AMentens N(2024)SPArch: A Hardware-oriented Sketch-based Architecture for High-speed Network Flow MeasurementsACM Transactions on Privacy and Security10.1145/368747727:4(1-34)Online publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1145/3687477
Jayaram RWoodruff DZhou S(2024)Streaming Algorithms with Few State ChangesProceedings of the ACM on Management of Data10.1145/36511452:2(1-28)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651145
Kallaugher JParekh OVoronova NMohar BShinkar IO'Donnell R(2024)Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming ModelProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649709(1805-1815)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649709
Show More Cited By

Index Terms

Counting large numbers of events in small registers
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
  2. Robustness
2. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Enumeration

Recommendations

Efficiently counting program events with support for on-line queries

The ability to count events in a program's execution is required by many program analysis applications. We represent an instrumentation method for efficiently counting events in a program's execution, with support for on-line queries of the event count. ...
A flexible way of counting large numbers approximately in small registers
Abstract
Robert Morris invented a novel, simple probabilistic algorithm for keeping approximate counts of large numbers of events, using small registers. One application is counting the number assigned to each of many categories of a very large number of ...
Exploiting virtual registers to reduce pressure on real registers

It is well known that a large fraction of variables are short-lived. This paper proposes a novel approach to exploiting this fact to reduce the register pressure for pipelined processors with data-forwarding network. The idea is that the compiler can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 21, Issue 10

Oct. 1978

76 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359619

Editor:
Robert L. Ashenhurst
The Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1978

Published in CACM Volume 21, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

counting

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

179
Total Citations
View Citations
1,962
Total Downloads

Downloads (Last 12 months)265
Downloads (Last 6 weeks)42

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sateesan AVliegen JScherrer SHsiao HPerrig AMentens N(2024)SPArch: A Hardware-oriented Sketch-based Architecture for High-speed Network Flow MeasurementsACM Transactions on Privacy and Security10.1145/368747727:4(1-34)Online publication date: 8-Aug-2024
https://dl.acm.org/doi/10.1145/3687477
Jayaram RWoodruff DZhou S(2024)Streaming Algorithms with Few State ChangesProceedings of the ACM on Management of Data10.1145/36511452:2(1-28)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3651145
Kallaugher JParekh OVoronova NMohar BShinkar IO'Donnell R(2024)Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming ModelProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649709(1805-1815)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649709
Braverman MGarg SLi QWang SWoodruff DZhang JMohar BShinkar IO'Donnell R(2024)A New Information Complexity Measure for Multi-pass Streaming with ApplicationsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649672(1781-1792)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649672
Piantadosi SGallistel C(2024)Formalising the role of behaviour in neuroscienceEuropean Journal of Neuroscience10.1111/ejn.1637260:5(4756-4770)Online publication date: 10-Jun-2024
https://doi.org/10.1111/ejn.16372
Kakimura NNitta R(2024)Randomized counter-based algorithms for frequency estimation over data streams in O ( log ⁡ log ⁡ N ) spaceTheoretical Computer Science10.1016/j.tcs.2023.114317984:COnline publication date: 12-Feb-2024
https://dl.acm.org/doi/10.1016/j.tcs.2023.114317
Gias AGao YSheldon MPerusquía JO’Brien OCasale G(2024)SampleHST-X: A Point and Collective Anomaly-Aware Trace Sampling Pipeline with Approximate Half Space TreesJournal of Network and Systems Management10.1007/s10922-024-09818-832:3Online publication date: 16-Apr-2024
https://dl.acm.org/doi/10.1007/s10922-024-09818-8
Johnen CKhattabi AMilani AWelch J(2024)Efficient Wait-Free Linearizable Implementations of Approximate Bounded Counters Using Read-Write RegistersStructural Information and Communication Complexity10.1007/978-3-031-60603-8_18(318-335)Online publication date: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_18
Jayaram RWoodruff D(2023)Towards Optimal Moment Estimation in Streaming and Distributed ModelsACM Transactions on Algorithms10.1145/359649419:3(1-35)Online publication date: 24-Jun-2023
https://dl.acm.org/doi/10.1145/3596494
Rinberg AKeidar I(2023)Intermediate Value Linearizability: A Quantitative Correctness CriterionJournal of the ACM10.1145/358469970:2(1-21)Online publication date: 18-Apr-2023
https://dl.acm.org/doi/10.1145/3584699
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Efficiently counting program events with support for on-line queries

A flexible way of counting large numbers approximately in small registers

Exploiting virtual registers to reduce pressure on real registers

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tag

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations