sliding window maximum

Question

I have a stream of tuples arriving in the following form: (timestamp,price). There is no pattern in the arrival of these data points (number of data points per minute is random). I need to be able to return the maximum price in the last hour at any point of time. What is the most efficient algorithm in terms of time complexity and space complexity separately to do this ? I thought of the following:

1. create 1 min candles of prices, which will reduce the storage but then wont be exactly correct
2. store the top K elements with their price and timestamps and update this list according to the current timestamp

Answer 1

In the worst case, there is no algorithm with better space complexity than storing all data points from the past hour. So, I think you should focus on optimizing time complexity. A reasonable data structure would be to store them in a balanced binary tree, keyed on timestamp, where each node is augmented with the maximum price over all descendants of that node. This achieves $O(n)$ space, if there are $n$ data points within the past hour, and $O(\log n)$ time per data point that you receive.

Answer 2

You will have to store one hour's worth of tuples. You can see this in the worst case of a series of descending prices over an hour. Say they were to come in one a minute starting at a price of 60. Then the first maximum would expire in one minute, then the second in the second minute and so on.

You should store the data in time order and only keep one hour's worth of tuples (using a FIFO queue). You haven't specified if timestamps are strictly in order as they come in. If not, then they will have to be kept sorted O(nlogn) - in which case its more efficient to store the tuples in order of price, then reading off the maximum is a case of reading the tuple at the end of the list.

However the data is sorted, you will have to do a linear scan either to find the maximum price (time ordered) or to remove tuples over one hour old (price ordered).

If time ordered you could keep scans of the data down by keeping track of the current maximum price and its position in the list. You compare each new tuple's price with the current maximum and if it's higher then this becomes the new maximum.

When the current maximum falls off the list (its age is greater than an hour), you do a linear scan to find the new maximum. This means doing a linear scan once an hour in the worst case.

If price ordered you can keep scans down by keeping track of the oldest timestamp and doing a linear scan for the next oldest when it expires.

Answer 3

For time complexity, it partly depends on where you want to improve the time. You could consider a FIFO where each record has the price and the timestamp and also something else: the largest price over every item that is as/more recent. This would mean an $O(n)$ operation for each batch of items that is inserted, but it would improve the time for fetching the maximum price, since you could peek at the front of the line, and pull off a few obsolete items (older than an hour) until you find an item no more than an hour old, and then the max price in that item is the value you want.

Or you could make each record contain the max price over all that is at least as old. In this case, to retrieve the max price over hour, it is an $O(1)$ operation if no old items need to be removed from the FIFO, but otherwise all the old items need to be purged and the max prices recomputed in $O(n)$.

But maybe what you want is a specialized B tree, in which each node contains as an extra field the largest price in the whole subtree. Whenever the B tree is restructured, all subtrees that are altered will require those fields to be recomputed. In the worst case, all deletions are happening at one end of the tree and all insertions at another... so I don't know if some of the extra balancing work of the tree is significant. After deleting an obsolete item, it would take $O(\log n)$ operations to update the nodes above it. Once a tree is purged of data more than an hour old (and all new data is added), only the tree root needs to be consulted to determine the maximum price in this case.

In all these instances, the best scheme with respect to time might depend on how frequently that price question needs to be answered compared to how frequently new data needs to be input.

I think the space complexities for these approaches are $O(n)$. With regard to space-saving you might think of having a data structure for each period of 10 minutes like so: 1:00-1:09; 1:10-1:19; etc. Then each price record only needs to contain a timestamp relative to the 10 minute threshold. If you precision is 1 sec, then each record only needs to distinguish which of 600 seconds the price is mamixum over. If it takes a second or more to compute the maximum anyway, then it should be precise enough to eliminate data that is 3600 +/- 1 second old.

The time precision is important. Is it close enough to count things minute by minute? If so, then you only need one record for each minute, and you can update the last minute's record with any new data if there are multiple data coming in for that minute. This will affect your storage by a significant factor, but this factor would only be $O(1)$.

Answer 4

The usual way to do this as a streaming algorithm is to store the entire window, but implement "add" and "evict" operations that are both fast (e.g. $O(1)$). Such operations are a common way to specify sliding window algorithms:

• The add function is called whenever an item enters the window;

• The evict function is called whenever an item leaves the window.

If we can implement both operations in $O(f(n))$, this implies a streaming algorithm that uses amortized$^1$ $O(f(n))$ time to process each element, and $O(n)$ space where $n$ is the maximum size of a window. As others have pointed out, there is no better streaming space complexity than storing all items, in the worst case.

$^1$The reason it is amortized constant instead of constant is that it's possible we get a large window built up, and then a single item (say, with a much larger timestamp) requires us to evict the entire window. So in the worst case, one addition to the window operation could take $O(n f(n))$. However, in total, each item is only added and evicted once from the window total, over time, so amortized time is constant.

So, the question that remains is: how do we implement add and evict efficiently? We can get $O(\log n)$ (maybe $O(1)$ is possible, I'm not sure). There are different data structures that could be used, but one possibility is a priority queue. Specifically, keep track of the priority queue $Q$ and the max $m$.

• To add an item with value $v$, add $v$ to $Q$; and if $v > m$, then set $m$ to $v$.

• To remove an item with value $v$, remove $v$ from $Q$. Then, inspect the largest element in the queue, and set $m$ to be that value.

Because priority queues can be implemented with $O(\log n)$ insertion and deletion and $O(1)$ inspection, and $n$ is both the size of the window and the size of the priority queue, this results in an $O(\log n)$ time complexity for both add and evict.

Answer 5

I believe you can solve this in $O(\log n)$ time per lookup by casting it as the Manhattan skyline problem where each "building" begins at the timestamp when a data point (timestamp, price) arrives, the height of the building is the price, and the width of each building is 1 hour. Here, n is also the space complexity, equal to the maximum number of events in any 1 hour window.

EDIT: Imagine sweeping a line of buildings left to right. The skyline is the outline of the roofs of the buildings. So, during the sweep, we want to output the height of the tallest building at the current point of the sweep.

Equivalently, we are streaming the input points in order of increasing timestamp. Whenever a point $(h, t)$ is encountered, that marks the beginning of a "building" whose time extent is $[t, t+1h]$. We want to output the height of the tallest building during the sweep, which corresponds to the maximum value in the previous 1 hour.

One algorithm for Manhattan skyline is to maintain the height of all "active" buildings in a data structure for which fetching and updating the maximum on each insertion and deletion is efficient. A MaxHeap should do the trick. The building corresponding to $(h, t)$ is inserted with value=$h$ at time $t$ and deleted at time $t+1$.