Finding top-K items in a sliding window

Question

Imagine we have a stream of bank transactions. Each transaction has a target account and some amount of money. I'd like to find top K accounts over some period of time (e.g. last 7 days) which received the maximum amount of money.

Are there any algorithms/papers that address this kind of problem?

Few clarifications:

1. I deliberately use bank accounts as an example since the same account can receive more than 1 transaction, and the transaction size is important. In this aspect the problem is very different from "Top-K most frequent items".
2. There are potentially infinitely-many window sizes (e.g. last day, last 2 days, last week etc etc). I wonder if there's an approach that would support this property without computing answers for all needed window sizes independently. (Or at least anything better than computing answers for all possible window sizes independently i.e. some way to derive an answer for window size X when we know answers for window sizes 2X and 0.5X or smth like that).

Answer 1

Your problem may be solved (perhaps with small modifications) by the algorithms TiTiCount, TiTiCount+ and TiTiCount+h. These are algorithms that allows you estimating the frequencies and finding frequent items in ad hoc windows in a data stream. In particular:

• TiTiCount uses a tilted timeframe for the representation of the past, which allows for frequency estimates for any user-specified windows in the past, using a small amount of memory;

• TiTiCount+ is an enhanced algorithm that makes use of a different tilted timeframe model. In this case, when a query for some item frequency in a particular window comes in, the query answering algorithm makes use of the information stored in the specified window of interest, but also uses the information stored in certain neighboring windows. Based on this extra information, the algorithm is able to refine the item frequency estimates, leading to more accurate results, with minimal additional processing;

• TiTiCount+h, an enhanced algorithm that extends sketches by adding concise histograms to the tilted timeframe windows. Histograms provide a more detailed representation of frequencies within each window, resulting in better frequency estimates for the query windows.

The algorithms are described in the following paper:

Michele Dallachiesa and Themis Palpanas. 2013. Identifying streaming frequent items in ad hoc time windows. Data Knowl. Eng. 87 (September, 2013), 66–90. DOI:https://doi.org/10.1016/j.datak.2013.05.007

The paper can be found here; the source code is also available here.

Answer 2

There probably are better ways but here goes.

Let each transaction be denoted $(i,A_i)$ and let them arrive in a stream.

Initialize a list $L:=[]$ which will be sorted on the second component.

For the first $K$ transactions insert $(i,A_i)$ into the proper position in $L.$ Let $L[1]$ denote the smallest entry in $L.$

Since the maximum amount seen so far is monotone increasing, if the next seen transaction $(i,A_i)$ satisfies $A_i\geq A_j$ for all $(j,A_j)$ in $L$ discard $L[1]$ from the list and then insert $(i,A_j)$ into its proper place in the list.

If there is a tie with $L[1]$ you can break ties arbitrarily if you wish to avoid the property that the latest $K^{th}$ largest transaction will end up in the list.