Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Exponential histograms: estimate failures in a recent event window

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

An exponential histogram summarizes the number of one-bits among the most recent W binary events. Every one creates a size-one bucket at the current event time. Whenever three buckets share a size, the two oldest merge into one bucket of double size. Buckets are ordered by their newest one-bit time; a bucket whose newest bit is before the window start expires. The sample also stores each bucket's oldest bit time. Buckets wholly inside the window contribute their exact sizes; if the oldest surviving bucket straddles the boundary, the estimate counts half of that bucket and exposes half its size as an additive uncertainty allowance. Zeros advance event time but add no bucket. This is an approximate count of events in a sliding window, not a list of exact failure timestamps.

Operational case

Across a twelve-event trace with an eight-event window, the model reports an estimate of six failures and a boundary allowance of two. Its retained bucket sizes are [1,1,2,4], newest first. The exact answer can differ from the estimate because a merged bucket can cross the window boundary without storing each bit's time. Expiring a bucket from its oldest timestamp would be wrong: it may still contain newer failures inside the window. A zero event still moves the cutoff forward, even though it creates no bucket. Changing the window width midstream is unsupported because old discarded bucket information cannot be recovered.

Working Python program

python
class RecentFailureHistogram:
    def __init__(self, window_size):
        if window_size <= 0:
            raise ValueError("positive window size required")
        self.window_size = window_size
        self.time = 0
        self.buckets = []  # Newest first: (number of ones, oldest one time, newest one time).

    def append(self, failed):
        if failed not in (0, 1, False, True):
            raise ValueError("one binary event required")
        self.time += 1
        if failed:
            self.buckets.insert(0, (1, self.time, self.time))
            self._compress()
        cutoff = self.time - self.window_size + 1
        self.buckets = [bucket for bucket in self.buckets if bucket[2] >= cutoff]

    def _compress(self):
        while True:
            counts = {}
            for bucket in self.buckets:
                counts[bucket[0]] = counts.get(bucket[0], 0) + 1
            oversized = next((size for size in sorted(counts) if counts[size] > 2), None)
            if oversized is None:
                return
            positions = [index for index, bucket in enumerate(self.buckets) if bucket[0] == oversized]
            newer, older = positions[-2:]
            merged = (2 * oversized, self.buckets[older][1], self.buckets[newer][2])
            del self.buckets[older]
            del self.buckets[newer]
            insertion = 0
            while insertion < len(self.buckets) and self.buckets[insertion][2] > merged[2]:
                insertion += 1
            self.buckets.insert(insertion, merged)

    def estimate(self):
        cutoff = self.time - self.window_size + 1
        total = 0.0
        for size, oldest, newest in self.buckets:
            if newest < cutoff:
                continue
            total += size if oldest >= cutoff else size / 2
        return total

    def uncertainty(self):
        """Maximum additive error implied by the one boundary bucket."""
        cutoff = self.time - self.window_size + 1
        return max((size / 2 for size, oldest, newest in self.buckets
                    if oldest < cutoff <= newest), default=0.0)


failure_window = RecentFailureHistogram(8)
for failed in (1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1):
    failure_window.append(failed)
print("estimate:", failure_window.estimate())
print("error allowance:", failure_window.uncertainty())
print("bucket sizes:", [bucket[0] for bucket in failure_window.buckets])

Output

Output
estimate: 6.0
error allowance: 2.0
bucket sizes: [1, 1, 2, 4]

Time, space, and tradeoff

At most two buckets of each power-of-two size remain, yielding O(log W) stored buckets for a fixed window width W. An estimate scans those buckets in O(log W) time. This direct Python append repeatedly scans and inserts in a small bucket list during cascading merges, costing O(log-squared W) in an unfavorable call; a tighter implementation can maintain counts and ordered links. The boundary bucket produces an additive error no greater than half its size in this model. Exact window counts require retaining more information, such as all recent bits or an exact queue of failure timestamps.

Common Mistakes

  • Do not expire a bucket merely because its oldest one-bit left the window.
  • Do not forget that a zero event advances the time boundary.
  • Do not report the half-bucket estimate as an exact count.
  • Do not resize the window after discarded history can no longer be restored.

Connected lessons

Compare this operation boundary with Count Sketch: estimate signed incident frequencies with row medians, Range-mode indexes: combine complete-block modes with fringe candidates, then complete the structure audit and decision quiz.

data structures
array-data-structure-guide
Storage details