Counting large numbers of events in small registers. (1978) (dl.acm.org)

In 1978 Robert Morris introduced a compact, probabilistic technique for counting very large numbers of events using tiny registers. Instead of storing a growing integer, the Morris counter stores a small value C that is incremented only with a probability that decreases exponentially with C (classically P(increment) = 2^{-C}). The estimator reconstructs the event count from C (roughly N ≈ 2^C − 1), giving an unbiased or nearly unbiased estimate with drastically reduced memory per counter. The trick is that the register grows logarithmically with the true count, so an 8–16 bit register can represent astronomically large counts. This idea matters to AI/ML and streaming systems because it inaugurated the family of probabilistic/approximate counting techniques: tiny memory footprints, fast updates, and amenability to high-throughput data streams. Key technical implications are the trade-offs between bias, variance, and memory: single Morris counters have high variance but that is reduced by running k independent counters and averaging (error scales like 1/√k). The method requires randomness and careful estimator/variance correction; it also led to later, more practical data structures (Flajolet–Martin, LogLog/HyperLogLog) that improved accuracy and mergeability. For memory-constrained telemetry, feature counting, and online analytics in ML pipelines, Morris-style counters remain a foundational primitive.