Monotonic queues and sliding windows

Why does a window aggregate's algebra set its memory, and how does a monotonic deque rescue max and min?

Monotonic queues and deques

The constraint, and why this item earns its place. Sliding-window aggregates divide into three classes by algebraic structure. That classification, not the window shape, decides the memory cost of every windowed computation you will write.

Sum is easy: add the new value, subtract the old. You cannot subtract a max. A naive sliding max is therefore O(window) per slide, and windows in streaming pipelines are often minutes wide over high-rate streams.

Domination pruning: the monotonic deque

A monotonic deque (double-ended queue) keeps only the elements that could still become the maximum. When a new element arrives, discard every element that is both older and smaller, because it is dominated for the rest of its life: it will leave the window first, and it is smaller anyway. Each element is pushed once and popped once, so the cost is O(1) amortized. The deque holds only the descending staircase of live candidates.

from collections import deque
def sliding_max(values, w):
    dq, out = deque(), []                  # dq holds indexes; their values decrease
    for i, v in enumerate(values):
        while dq and values[dq[-1]] <= v:  # older and not larger: dominated
            dq.pop()
        dq.append(i)
        if dq[0] <= i - w:                 # the front fell out of the window
            dq.popleft()
        if i >= w - 1:
            out.append(values[dq[0]])      # the front is the window maximum
    return out

That principle recurs well beyond windows. It is skyline / Pareto pruning. It is the retention rule in the Space-Saving and Misra-Gries heavy-hitter algorithms (Probabilistic structures). It is the logic behind keeping only frontier candidates in any search. Discard what is dominated on every dimension that matters is the cheapest form of state reduction, and it costs no accuracy at all.

The honest comparison: panes

The deque is not what most systems use. Pane (slice) decomposition splits the window into fixed slices, aggregates each slice once, and combines the slices for each output. Its cost is O(window/slide) combines per emission. That is worse asymptotically, yet it wins in practice, because it:

• generalizes to any associative function;
• parallelizes across slices;
• distributes as keyed state;
• tolerates out-of-order arrival inside a slice.

The monotonic deque needs strictly sequential, in-order, single-threaded access, which is exactly what a distributed stream processor does not have. Use the deque in a single-threaded hot loop. Use panes in a system like Flink.

The holistic row is the bridge to Probabilistic and sketch structures: trading correctness for space

When neither inversion nor decomposition works (a median over a window, distinct users in the last hour, top-k items in a stream), the only remaining escapes are:

• keep the full window: memory proportional to window × key cardinality, which is how streaming jobs run out of memory; or
• give up exactness.

That is where sketches enter, and it is why Probabilistic structures is not a collection of clever tricks. It is the forced answer to a class of aggregate that has no exact bounded-state solution.