Sliding Windows and Exponential Histograms for Recent Data

A whole-stream summary answers a question about everything that ever arrived. A sliding-window summary answers the same question about the last $W$ items, or the last $T$ seconds, and the answer changes as items expire even though no new data has arrived. That requirement breaks every summary built on an invariant that assumes data is only ever added: a minimum that was computed over all data is not the minimum over a window, and a counter that only increases cannot forget.

The window formulation is also where the distinction between arrival order and event time first becomes a correctness issue rather than a nuisance.

Why deletion changes the problem

Consider counting the number of 1-bits in the last $W$ positions of a bit stream. The whole-stream count is one integer. The windowed count requires subtracting the bit that leaves the window, so the algorithm must remember something about the position of each 1.

A naive approach keeps a queue of the last $W$ bits and maintains a running sum. That is exact, costs $W$ bits, and is what a straightforward implementation does. When $W$ is a billion and the available memory is a kilobyte, the queue is impossible, and the problem becomes: maintain a count over a window without storing the window.

The exponential histogram answers this for the count of ones. It stores buckets, each covering one interval of window positions and holding the number of ones in that interval, so the buckets partition the window. Every arriving bit starts a new bucket of length one, holding either a 0 or a 1. When a bucket falls entirely out of the window, its count is subtracted from the total. When too many buckets share one length, adjacent buckets of that length are merged into a single bucket of twice the length — merging preserves the count exactly, because the merged interval is the union of two adjacent ones.

The merge rule and the 1 + epsilon bound

The rule is: merge two adjacent buckets of the same length when there are more than a fixed number of buckets of that length. If at most $M$ buckets are allowed per length class, and every bucket length is a power of two, then the number of buckets is $O(M \log W)$, and each bucket’s count is exact for the interval it spans; it is the interval boundaries, not the counts, that the merge rule makes coarse.

The error analysis is a telescoping argument. Merging two buckets of size $2^j$ into one of size $2^{j+1}$ combines their counts; the resulting bucket’s count is the exact number of ones in the union of the two intervals, so merging itself introduces no error. Error enters only when a bucket is split by the window boundary — a bucket that straddles the boundary contributes its whole count or none, and the discrepancy is bounded by the bucket’s size.

With $M$ buckets per length class, the merge rule keeps the largest class present to a $1/M$ fraction of the window’s mass, and the smaller classes that also straddle the boundary are geometrically smaller and together add up to the same order. The relative error of the window count is therefore $O(1/M)$. Choosing $M = \lceil 1/\varepsilon \rceil$ gives a $1 + \varepsilon$ multiplicative error with $O((1/\varepsilon) \log W)$ buckets, each holding a start position, a length, and a count.

The same construction works for sums of arbitrary non-negative values, with bucket counts replaced by bucket sums. It does not work for minimum or maximum, where merging destroys the very thing being tracked, and it does not work for distinct counts, where the union of two buckets has a distinct count that is not derivable from the two buckets’ distinct counts. Those need different techniques: a windowed minimum uses monotonic dequeues over a bounded window, and windowed distinct counting uses a per-window HyperLogLog rebuilt on a schedule, or the more elaborate constructions that maintain several overlapping sketches.

class ExpHistogram:
    """Counts ones in the last W positions; error O(1/M) of the window count."""

    def __init__(self, window, max_per_class):
        self.window = window
        self.M = max_per_class
        self.buckets = []      # [start, length, count], oldest first
        self.total = 0         # sum of the counts of the buckets in the window
        self.pos = 0

    def add(self, bit):
        self.pos += 1
        self.buckets.append([self.pos, 1, bit])
        self.total += bit
        self._expire()
        self._compress()

    def _expire(self):
        cutoff = self.pos - self.window
        # a bucket is dropped only once it lies entirely before the window
        while self.buckets and self.buckets[0][0] <= cutoff:
            self.total -= self.buckets.pop(0)[2]

    def _compress(self):
        # merge two adjacent buckets of equal length while more than M share it
        merged = True
        while merged:
            merged = False
            for i in range(len(self.buckets) - 1):
                a, b = self.buckets[i], self.buckets[i + 1]
                if a[1] == b[1] and sum(x[1] == a[1] for x in self.buckets) > self.M:
                    self.buckets[i:i + 2] = [[a[0], 2 * a[1], a[2] + b[2]]]
                    merged = True
                    break

The _compress loop above rescans the bucket list every time it merges, which is quadratic in the number of buckets — acceptable for a listing, not for a stream. An implementation that keeps a linked list per length class merges the two oldest buckets of a class in $O(1)$ and never rescans, which brings the amortised cost per element down to $O(\log W)$. The total field is the answer: it is exact for the buckets it holds, and its error is the mass in the bucket that straddles the window boundary, counted in full or not at all.

Event time, watermarks, and the window that is not a window

Everything above assumes the window is defined over arrival position. Almost every real system defines it over event time: the last five minutes of events, where the timestamp is carried in the event payload. Arrival order and event time diverge whenever the source is delayed, buffered, or replaying.

The consequence is that an event arriving now may belong in the middle of the window, not at its end. A summary that appends every arrival to the newest bucket is computing a window over arrival order, and its answer will disagree with the event-time answer by however much the stream is out of order. For a stream that is mostly in order the disagreement is small; for a stream that aggregates from many sources with different latencies it can be total, since a batch of late events can arrive after the window they belong to has closed.

The standard mechanism is a watermark: a declaration that no event with timestamp earlier than $t$ will arrive. Given a watermark, a system can safely close windows ending before $t$ and emit their results, and can hold windows that are still open. The cost of the watermark is latency — the system cannot emit until the watermark advances — and the cost of a wrong watermark is either dropped data (if the watermark is too aggressive) or unbounded state (if it never advances, as happens when one source stalls).

Exponential histograms do not accommodate out-of-order insertion, because the bucket structure is a sequence ordered by arrival. A late event must be inserted into a bucket whose position is already fixed, which changes that bucket’s count and therefore the totals of every bucket merged into it. Implementations that must handle late data either keep a small buffer of recent events and recompute affected buckets, or fall back to a coarser structure — a set of fixed-width time slices, each with its own exact count — where late insertion is a simple increment to one slice.

Windows over counts versus windows over time

The two formulations behave differently under a changing arrival rate, and the difference is not cosmetic.

A count-based window of $W$ items covers a time span that depends on the rate. At 1000 events per second, $W = 100{,}000$ covers a hundred seconds; at 10 events per second, it covers nearly three hours. A rate detector built on a count window will therefore have a response time that varies with load, which is usually the opposite of what is wanted: the detector is least sensitive exactly when traffic is low.

A time-based window of $T$ seconds covers a count that varies with the rate, so the summary’s error — which is relative to the count — stays proportional to the current volume. That is usually the correct behaviour for anomaly detection, where the question is “is the current rate unusual” rather than “is the current count unusual”.

The memory cost differs too. A time-based window with exponential buckets needs buckets keyed by timestamp ranges and must expire them by time, which requires the bucket structure to support ordered expiration — the same operation as the count-based version, with the boundary computed from the timestamp instead of the position. A count-based window needs only a position counter, which is cheaper and immune to clock skew.

Where the guarantee leaks

Four conditions are needed for the $1 + \varepsilon$ bound, and real deployments violate each of them in recognisable ways.

Non-negative values. Bucket merging preserves sums only when the summands are non-negative. With signed values, two buckets whose sums cancel produce a merged bucket with a small sum that hides large internal variation, and the boundary-straddling error is no longer bounded by the bucket size. For signed windows, the usual approach is two histograms, one for each sign.

A bounded window. The analysis assumes $W$ is fixed and known. A window that grows — “all data since the service started” — degenerates into a whole-stream summary and the bucket count grows with $\log W$ without bound. A window that shrinks must discard buckets from the old end, which the structure supports, but the error bound then applies to the smaller window and is looser in absolute terms.

Monotone arrival positions. New bits are appended at the newest end and expiration walks from the oldest end, so the structure assumes each arrival belongs after every arrival before it. Data that arrives out of order breaks that assumption directly, which is the same failure described in the event-time section above.

A single merge policy. Mixing bucket sizes — merging some classes more aggressively than others — changes the constant in the error bound and can change it from a factor to an additive term. The bound in the original analysis depends on all classes having the same cap $M$.

The relation to whole-stream sketches

A windowed summary is not a whole-stream summary with a forgetting mechanism bolted on; it is a different object with a different error model. A whole-stream sketch’s error is relative to the total, which grows, so the absolute error grows while the relative error stays fixed. A windowed summary’s error is relative to the window’s content, which fluctuates, so the absolute error fluctuates with the traffic.

That difference shows up when the two are composed. A system that keeps a whole-stream Count-Min sketch for per-key counts and a windowed histogram for recent volume is answering two questions with two error models, and a query that joins them — “which keys grew fastest in the last minute” — inherits the worse of the two. The clean design is to keep windowed versions of both, which doubles the memory and requires the sketch to support subtraction of an old window’s contribution. Linear sketches support that subtraction exactly, which is one more reason the linear formulation in the streaming model is the useful one: a sketch of the last window can be computed as the difference of two cumulative sketches, at the cost of the cancellation error that comes with subtracting two similar large numbers.