Two-Stack Sliding-Window Aggregation: A Classic Streaming Algorithm

What Is Two-Stack Sliding-Window Aggregation

Two-Stack Sliding-Window Aggregation is an efficient algorithm for stream computing that uses two stacks to maintain a sliding window. This allows element insertion and expiration-based deletion to complete in amortized O(1) time, while querying the aggregated value within the window in real time.

This idea sparked discussion on Hacker News (original post). Its core value lies in transforming the seemingly scan-intensive structure of a "sliding window" into two directionally complementary stacks—one handling "entry" and the other handling "exit"—so that queries only need to merge the aggregate results of the two.

Why Sliding Windows Need a Special Algorithm

The Naive Implementation of a Sliding Window

The most straightforward approach to a sliding window is to maintain a queue: each new element is added to the tail, when the window exceeds its limit the head is popped, and queries traverse the entire window to compute the aggregate. With a window size of k, each query costs O(k), which is noticeably expensive in high-frequency query scenarios.

Monotonic Queues Solve Part of the Problem

For problems like "find the window maximum/minimum," a monotonic queue can reduce queries to amortized O(1). However, monotonic queues rely on the monotonicity of comparison operations and do not directly apply to aggregates like sum, count, or average—because these operations don't satisfy the property that "popping a smaller element doesn't affect the result."

The cleverness of two-stack aggregation is that it covers any aggregations satisfying associativity (sum, count, extrema, or even more complex merges), not just the class of problems monotonic queues can handle.

Amortized analysis is the key analytical tool here. It doesn't focus on the worst-case cost of a single operation, but rather on the average cost across a sequence of operations. The classic example is dynamic array resizing: a single insertion may trigger an O(n) copy, but the total cost of n consecutive insertions is still O(n), so the amortized cost per insertion is O(1). Likewise, in two-stack aggregation, moving back to front is O(n) for a single operation, but since each element is moved only once in its lifetime (popped from back, pushed onto front, then staying on front until expiration), the total cost of any consecutive sequence of operations is proportional to the number of elements, giving amortized O(1) per insertion/deletion/query. Understanding amortization prevents being misled by the surface appearance of "an operation that's particularly slow"—as long as the caller doesn't require a strict worst-case single-operation response time, amortized O(1) is fully equivalent to O(1) in engineering terms.

The Core Mechanism of the Two-Stack Structure

Division of Labor Between the Two Stacks

Split the sliding window into two segments, front and back:

• back stack: New elements are pushed onto the top, handling "entry into the window."
• front stack: Elements are popped from here in FIFO order, handling "exit from the window."

Each stack additionally maintains an "aggregate value array": each position in the stack records the aggregate result from the stack bottom to that position. This way any stack's aggregate value can be read in O(1).

When to Move back to front

When a head element needs to be popped but the front stack is empty, all elements of the back stack are popped in sequence and pushed onto the front stack. This operation reverses the order of elements, bringing the earliest-entered element back to the top of the front stack so it can be correctly popped.

A single move is O(n), but each element is moved only once in its lifetime, so the amortized complexity remains O(1). This is a classic scenario for amortized analysis.

How to Merge During Queries

The window's aggregate value = front stack's aggregate value ⊕ back stack's aggregate value, where ⊕ is the merge operation for the aggregation. Since each stack already maintains a valid aggregate from its bottom to the current position, a query requires just one merge and is O(1).

Use Cases and Engineering Value

Real-Time Monitoring and Metric Systems

In monitoring systems, rolling metrics like "requests in the last N seconds" and "P99 latency in the last N seconds" are frequently needed. Two-stack aggregation lets these metrics be updated incrementally as data arrives, instead of rescanning the window each time.

Comparison with Other Approaches

Approach	Query Complexity	Supported Aggregations
Naive queue	O(k)	Any
Monotonic queue	Amortized O(1)	Extrema only
Two-stack aggregation	Amortized O(1)	Any associative aggregation

For scenarios requiring "any aggregation + high-frequency queries," the two-stack approach is currently a very elegant compromise. If the aggregation operation is reversible (e.g., sum), you can also use an "add in, subtract out" approach, but once irreversible aggregations are involved (extrema, approximate medians), the two-stack approach is more robust.

t-digest and GK summaries are two commonly used small-memory approximate quantile algorithms. t-digest ensures higher accuracy at tail quantiles (like P99) by "dynamically adjusting cluster coarseness based on quantile position," making it suitable for monitoring latency and other scenarios focused on extremes; GK summary (Greenwald-Khanna) uses counters with error bounds to provide deterministic quantile approximation guarantees. In contrast, two-stack sliding-window aggregation deals with the structural expiration problem of "the most recent N elements." It guarantees exact results but does not address "estimating quantiles memory-efficiently over a very large window." The two are often used together: two-stack handles exact sums and counts for fixed windows, while non-associative metrics like quantiles are handled separately by approximate structures like t-digest.

A Few Implementation Details

Associativity of the Aggregation Is a Prerequisite

Two-stack relies on the aggregation operation satisfying associativity: the merge order doesn't affect the result. Sum, count, extrema, and set union all satisfy it, but the average itself doesn't—it needs to be rewritten as two separate associative quantities ("sum maintenance + count maintenance") with a division at query time.

Associativity means the operation satisfies (a ⊕ b) ⊕ c = a ⊕ (b ⊕ c), i.e., the "grouping" of merges doesn't affect the final result. This is a prerequisite for the two-stack approach because window aggregation is essentially merging the aggregate values of the front and back stacks, and the internal aggregates of the two stacks are accumulated at different times; if associativity doesn't hold, a change in accumulation order will cause the result to drift. Sum, count, maximum, minimum, bitwise OR, and set union all satisfy associativity; but average, median, and variance do not—the correct way to handle them is to split the problem into several associative components (e.g., average into sum and count, variance into sum, sum of squares, and count), performing the final division or square root only at query time. The reason approximate streaming structures like t-digest and GK summaries are complex is precisely that they must maintain controllable error on statistics that don't satisfy simple associativity.

Empty Stacks and Boundary Handling

Querying when front is empty, or querying before the window is full, are boundaries prone to errors. Engineering implementations typically give empty stacks an identity element, so that "empty stack aggregation" can participate in merges without breaking the result.

When to Switch Approaches

Two-stack aggregation assumes the window follows a "clean-cut" fixed-length or time-based expiration policy. If the window boundaries are more complex (e.g., weighted windows, multi-level windows), or the aggregation itself requires exact medians or quantiles, two-stack is no longer optimal and you need to turn to more specialized streaming algorithms (approximate structures like t-digest, GK summaries, etc.).

Summary

Two-Stack Sliding-Window Aggregation uses a simple data structure trick to reduce sliding-window queries from O(k) to amortized O(1), while maintaining support for a broad range of aggregation operations. Its value isn't in novelty, but in being reliable, predictable, and easy to implement—which is why it has long held a place in streaming libraries and real-time metric systems. For engineers working on backend or data infrastructure, understanding this mechanism allows quickly determining which window structure to use when designing metric systems.

One-line Summary

Two-stack sliding-window aggregation uses two stacks to achieve amortized O(1) queries over any associative aggregation in a streaming window.

Paragraph Summary

Two-Stack Sliding-Window Aggregation is a streaming algorithm that uses two stacks—back and front—to handle element entry and exit respectively. Each stack additionally maintains an array of aggregate values from the stack bottom to the current position, enabling insertion, expiration-based deletion, and window aggregate queries in amortized O(1) time. Its core trick is to move the entire back stack over (reversing order) when front is empty; since each element is moved only once, the amortized complexity remains O(1), and queries only need to merge the two stacks' aggregate values. Compared to a naive queue's O(k) queries and a monotonic queue's limitation to extrema only, the two-stack approach supports sum, count, extrema, and any associative aggregation. The article also discusses how averages must be split into sum + count, empty-stack identity elements, and alternatives like t-digest for more complex windows.