Exponential & Smooth Histograms

Summaries That Age and Expire

A sliding window asks about recent history rather than everything ever seen. If a service receives one event per second and uses a 60-second window, the answer at time \(t\) concerns timestamps \(t-59,\ldots,t\). The oldest event expires whenever a new second arrives. Exact storage is easy for 60 bits, but not for millions of keys, long windows, or richer statistics.

An exponential histogram summarizes the number of ones in a binary window. Imagine packing recent receipts into boxes. New receipts begin in size-one boxes. When too many boxes have the same size, merge the two oldest into one double-size box. Recent history stays detailed; old history becomes coarse. Bucket sizes are powers of two, and each bucket records enough time information to determine when it lies completely outside the window.

For a tiny example with window width \(W=8\), suppose the retained one-buckets from newest to oldest have sizes \(1,1,2,4\). Their total represented count is eight. If the window boundary cuts through the oldest size-four bucket, its exact in-window contribution is unknown between zero and four. Counting half of that bucket yields estimate \(1+1+2+2=6\), with absolute boundary uncertainty at most two.

This deep dive builds on sliding windows and time decay by explaining how deletion-by-age can be approximated without storing every event. A bucket invariant limits how many buckets of each power-of-two size exist and keeps them in timestamp order. Expiration removes a bucket only when its newest item is no longer in the window; before that, the oldest remaining bucket may straddle the boundary. Approximation error is charged entirely to that boundary bucket for binary counting.

A smooth histogram generalizes the landmark idea. Instead of power-of-two counts, it runs a base streaming summary from several start times and removes redundant starts when function values are sufficiently close. This is valid only for a function satisfying an appropriate smoothness condition: roughly, if deleting an old prefix changes a suffix's value only slightly now, appending the same future continuation must not make that deletion suddenly important. Exponential histograms and smooth histograms share an aging pattern but are not identical algorithms.

Time semantics are part of correctness. This page uses ordered integer timestamps and the inclusive window \([t-W+1,t]\). Event-time disorder, late data, negative updates, weighted events, and clock resets require explicit variants or buffering.

Exponential Buckets and Smooth Functions

For the binary-count problem, every incoming one creates a bucket of size one with end timestamp equal to the current time. Zeros advance time but create no bucket. Bucket sizes are powers of two. If more than \(r\) buckets of size \(2^j\) exist, merge the two oldest into one size-\(2^{j+1}\) bucket. The merged bucket's end timestamp is the newer end time of the two source buckets. Merging may cascade.

Buckets are kept newest to oldest. At query time \(t\), let \(L=t-W+1\). Delete every oldest bucket whose end timestamp is strictly less than \(L\): even its newest one is outside the window, so the entire bucket is expired. The new oldest bucket may start before \(L\) and end at or after \(L\); it alone is ambiguous. Estimate the count by summing all newer bucket sizes and a chosen fraction—classically one half—of this boundary bucket.

Why logarithmic space? The maximum bucket size is at most the number of ones seen in the relevant history, and there are \(O(\log W)\) size classes for a width-\(W\) binary window. Keeping \(r=O(1/\varepsilon)\) buckets per size yields \(O((1/\varepsilon)\log W)\) buckets. The boundary bucket's size is controlled relative to newer represented mass by the same-size occupancy invariant, producing \(O(\varepsilon)\) relative error. Exact constants depend on whether the implementation allows \(r\), \(r+1\), or another count before merging and how it estimates the boundary bucket; document the convention instead of transplanting a formula.

The classic two-buckets-per-size DGIM convention gives a coarse constant-factor count estimate. Increasing the per-size allowance improves accuracy while using more memory. An exact ring buffer uses \(O(W)\) bits but has no approximation error. Fixed time bins are simple but can have an entire bin of boundary error and do not adapt their granularity geometrically.

Smooth histograms abstract the “keep only significant ages” principle. Let \(f\) be a nonnegative monotone function on streams. One common \((\alpha,\beta)\)-smoothness form says: for a suffix \(B\) of \(A\), if \(f(B)\ge(1-\beta)f(A)\), then for every common continuation \(C\), \[ f(B\circ C)\ge(1-\alpha)f(A\circ C). \] Maintain base summaries starting at selected landmarks. If two neighboring starts currently have sufficiently close values, the older intermediate start can be removed because smoothness says that closeness remains controlled after future arrivals. At the window boundary, choose the summaries that bracket the desired start and apply the base estimator's guarantee plus the smoothness loss.

This extension is theorem-driven. A function with abrupt sensitivity to one expired item may not satisfy useful smoothness parameters; running the landmark deletion rule anyway has no guarantee. The base summary's approximation, landmark thinning, late-data policy, and window boundary each contribute separate error obligations.

flowchart TD
    A[Ordered timestamped arrival] --> B{Binary one?}
    B -->|yes| C[Create size-one bucket]
    B -->|no| D[Advance time only]
    C --> E{Too many buckets of a size?}
    E -->|yes| F[Merge two oldest equal sizes]
    F --> G[Double size and keep newer end time]
    G --> E
    E -->|no| H[Expire buckets wholly before window]
    D --> H
    H --> I[Sum newer buckets plus boundary estimate]
    I --> J[Error charged to oldest retained bucket]
    A --> K{Richer statistic is smooth?}
    K -->|yes| L[Maintain and thin landmark summaries]
    K -->|no| M[No smooth-histogram guarantee]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,D,E,H navy;
    class C,F,G purple;
    class I,J,L teal;
    class K,M crimson;

Bounding Boundary-Bucket Error

Let the nonexpired buckets from newest to oldest have sizes \(b_1,\ldots,b_m\), with \(b_m\) the possible boundary bucket. All buckets \(b_1,\ldots,b_{m-1}\) lie fully inside the window, so their contribution is exact. If \(q\) of the \(b_m\) represented ones are actually inside, then \[ C=\sum_{i=1}^{m-1}b_i+q,\qquad 0\le q\le b_m. \] The half-bucket estimate is \[ \widehat C=\sum_{i=1}^{m-1}b_i+\frac{b_m}{2}, \] so \(|\widehat C-C|\le b_m/2\). Stronger relative guarantees follow by proving that the occupancy invariant forces enough newer mass compared with \(b_m\). That proof must match the exact merge threshold and the fact that a retained boundary bucket normally contains at least one in-window one.

Consider buckets \(1,1,2,4\). Newer exact mass is four. If exactly one of the oldest bucket's four ones is in-window, exact count is five and the estimate is six, error \(+1\). If three are in-window, exact is seven and the estimate is six, error \(-1\). The maximum half-bucket uncertainty is two.

Expiration mistakes are usually worse than approximation. Using a bucket's oldest timestamp instead of its newest can delete it while it still contains valid ones. Keeping a bucket whose newest timestamp is before the window start includes wholly expired mass. Event-time disorder can break chronological bucket coverage unless the system buffers to a watermark or uses a late-data-aware design.

The algorithm is deterministic once event order and merge convention are fixed; no hash independence is involved. Scale boundaries include timestamp rollover, bucket-size overflow, one histogram per high-cardinality key, and long zero runs. Zeros advance the clock and may expire buckets even though they add no count.

from dataclasses import dataclass
from collections import deque

@dataclass
class Bucket:
    size: int
    end: int

class ExponentialHistogram:
    def __init__(self, window, per_size=4):
        if window < 1 or per_size < 2:
            raise ValueError("positive window and at least two buckets per size")
        self.window = window
        self.per_size = per_size
        self.time = -1
        self.buckets = []  # newest to oldest

    def update(self, bit, timestamp=None):
        if bit not in (0, 1):
            raise ValueError("binary input required")
        timestamp = self.time + 1 if timestamp is None else timestamp
        if timestamp <= self.time:
            raise ValueError("timestamps must increase")
        self.time = timestamp
        if bit:
            self.buckets.insert(0, Bucket(1, timestamp))
            self._compress()
        self._expire(timestamp)

    def _compress(self):
        size = 1
        while True:
            positions = [i for i, b in enumerate(self.buckets) if b.size == size]
            if len(positions) <= self.per_size:
                larger_exists = any(b.size > size for b in self.buckets)
                if not larger_exists:
                    break
                size *= 2
                continue
            newer_old, oldest = positions[-2], positions[-1]
            merged_end = self.buckets[newer_old].end
            self.buckets.pop(oldest)
            self.buckets.pop(newer_old)
            insert_at = sum(b.end > merged_end for b in self.buckets)
            self.buckets.insert(insert_at, Bucket(size * 2, merged_end))
            size *= 2

    def _expire(self, now):
        start = now - self.window + 1
        while self.buckets and self.buckets[-1].end < start:
            self.buckets.pop()

    def estimate(self, now=None):
        now = self.time if now is None else now
        if now < self.time:
            raise ValueError("cannot query the past")
        self._expire(now)
        if not self.buckets:
            return 0.0
        total = sum(b.size for b in self.buckets)
        return total - self.buckets[-1].size / 2

    def boundary_bound(self):
        return 0.0 if not self.buckets else self.buckets[-1].size / 2

def run(bits, window, per_size=4):
    eh, exact = ExponentialHistogram(window, per_size), deque()
    for t, bit in enumerate(bits):
        eh.update(bit, t)
        exact.append((t, bit))
        while exact and exact[0][0] < t - window + 1:
            exact.popleft()
        truth = sum(bit for _, bit in exact)
        assert abs(eh.estimate() - truth) <= eh.boundary_bound()
    return eh, sum(bit for _, bit in exact)

normal = [1,0,1,1,0,1,0,0,1,1,1,0,1,0,1,1]
eh, truth = run(normal, window=8)
zeros, zero_truth = run([0] * 30, window=10)
burst, burst_truth = run([1] * 20 + [0] * 20, window=16)
assert zeros.estimate() == zero_truth == 0

try:
    eh.update(2, 100)
    raise AssertionError("nonbinary input accepted")
except ValueError:
    pass

try:
    eh.update(1, eh.time)
    raise AssertionError("nonincreasing timestamp accepted")
except ValueError:
    pass

print("normal estimate/exact:", eh.estimate(), truth)
print("burst estimate/exact:", burst.estimate(), burst_truth)
print("buckets:", [(b.size, b.end) for b in eh.buckets])

Recent Counts Under Bursty Traffic

In a teaching case, write a binary stream on cards and maintain at most two buckets per size. Every merge preserves the total number of represented ones; every query highlights the sole boundary bucket. Long zero runs demonstrate that time advances even when no bucket is created.

At professional scale, a gateway may estimate successful requests in the last ten minutes for many routes. Per-route exponential histograms avoid a full 600-second ring buffer, but high key cardinality can still dominate memory. The configuration must version window width, timestamp unit, inclusive-boundary rule, per-size allowance, estimate formula, counter widths, and late-data policy.

A telemetry service may need recent \(F_2\), distinct count, or another statistic. It should use a smooth histogram only after selecting a base streaming algorithm and verifying the required smoothness theorem. “It worked for counts” is not proof. Run exact replay windows, decompose base and windowing error, and validate at burst boundaries.

Adversarial or failure cases include a burst packed into the boundary bucket, timestamps arriving out of order, producers manipulating event time, and clock jumps that expire everything. Watermarks and bounded lateness can define when results become final. Evidence invalidating deployment includes bucket multiplicity violations, error beyond the boundary certificate, nonmonotone time, overflow, or memory growing faster than the documented logarithmic envelope.

flowchart TD
    A[Define hard window time semantics and statistic] --> B{Binary count?}
    B -->|yes| C[Evaluate exponential histogram]
    B -->|no| D{Statistic has smoothness theorem?}
    D -->|yes| E[Choose smooth histogram and base summary]
    D -->|no| F[Use exact window or another method]
    C --> G[Set error and buckets per size]
    E --> G
    G --> H[Fix watermark lateness and overflow policy]
    H --> I[Validate on exact bursty windows]
    I --> J{Invariants error and memory acceptable?}
    J -->|no| K[Reject resize or repair semantics]
    J -->|yes| L[Version and deploy]
    L --> M[Monitor boundary error and late data]
    M --> N{Assumptions still hold?}
    N -->|yes| M
    N -->|no| K
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
    classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
    class A,B,D,H navy;
    class C,E,G purple;
    class I,L,M teal;
    class F,J,K,N crimson;

Trace a Window Histogram

Mastery starts with a complete state trace. For every timestamp, record the incoming bit, buckets newest to oldest, every merge, window start, expired buckets, exact count, estimate, and boundary bound. Prove that merging preserves represented ones and that only the oldest retained bucket can straddle the boundary.

Debug the mistakes that most often masquerade as approximation: merging the newest equal-size buckets instead of the oldest, retaining the older timestamp on merge, expiring from a bucket's oldest event, failing to advance time on zero, and accepting out-of-order events. Each should be connected to a broken invariant and a concrete counterexample.

For extension, formalize a smoothness condition for a chosen statistic, identify a base streaming estimator, and account separately for base error and landmark error. Compare strict windows with exponential decay and session windows. This bridges sliding counts to recent norms, distinct counts where supported, and distributed event-time processing.