H2 Morris Counter

I was thinking about the Morris counter algorithm and wondered if it would be possible to combine it with the H2 histogram encoding to have more control over the standard deviation of the approximation in exchange for spending more bits to represent the same value range.

It turns out the answer is yes:

// Probabilistic increment based on the bin width at the current counter value
function increment(counter, a, b) {
  return counter + (Math.random() < 1/h2(counter, a, b).binWidth)
}

// Expected value of the H2 counter
function estimatedValue(counter, a, b) {
    return h2(counter, a, b).lower
}

// A mini H2 histogram decoder implementation for values <= 2^32-1.
// Returns the lowest value in, and bin size of, the `index`-th bin.
function h2(index, a, b) {
  const c = a + b + 1;
  const binsBelowCutoff = u32(1 << (c - a));
  if (index < binsBelowCutoff) {
    // we're in the linear section of the histogram; each bin is 2^a wide
    return {
      lower: u32(index << a),
      binWidth: u32(1 << a)
    }
  } else {
    // we're in the log section of the histogram; 2^b bins per log segment
    const logSegment = c + ((index - binsBelowCutoff) >>> b);
    const binOffset = index & (u32(1 << b) - 1);
    return {
      lower: u32(1 << logSegment) + u32(binOffset << (logSegment - b)),
      binWidth: u32(1 << (logSegment - b))
    }
  }
}

function u32(x) {
  return x >>> 0;
}

The idea is that every integer represents a random variable whose expected value is the lower edge of the corresponding histogram bin, since this way the index 0 can represent the value 0. The number of integers that share this encoding is the bin width, so the probability of ascending to the next bin is 1 / bin width.

The parameter a controls the bin width on the low end of the value range (typically set to 0 to represent small integers exactly), while the parameter b controls relative error on the high end by determining the number of linear subdivisions within the upper log segments. Larger values of b increase the quality of the approximation by increasing the number of bins covering the value range.

When used as the basis for a histogram, the H2 encoding upper-bounds the relative error for large values. But in the context of probabilistic counters the H2 encoding does not prevent the value estimate from being wildly far away from the true value, since an unlikely series of coin flips can cause the value estimate to drift very far away. But, compared to the Morris counter, it does allow you to spend more bits to decrease the expected relative error and variance of the approximation.

As a special case, when a and b are both zero, this counter is almost the same as the standard Morris counter, with the only difference being that the positive estimated values are all exact powers of two.

Here’s the code for a Morris counter for comparison:

// Probabilistic increment as per the Morris counter algorithm
function morrisIncrement(counter) {
  return counter + (Math.random() < 1/Math.pow(2, counter))
}

// Expected value of the Morris counter
function morrisEstimatedValue(counter) {
  return 2 ** counter - 1
}

References:

• The original paper by Robert Morris is Counting Large Numbers of Events in Small Registers, published in 1977
• The mini H2 encoding above was originally written for iopsystems/h2-histogram-js.
• The reference H2 histogram implementation is in Rust at rustcommon/histogram.
• There’s a visual explanation of the a and b histogram parameters in this notebook.

Thanks to Sean Lynch, Brian Martin, Yao Yue, and Mihir Nanavati for a discussion that lead to these implementations. Sean made a “morris float” which applies the same probabilistic approach directly to the exponent and mantissa of an f32.