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).
  • 1
    $\begingroup$ What did you try? Where did you get stuck? What's the best known bound for similar problems that you've looked up? $\endgroup$
    – jbapple
    Sep 1 '21 at 19:01
  • $\begingroup$ @jbapple I wasn't able to find anything that would fit or come close to solving this problem. I think I made a mistake when described the problem and created a wrong impression that the window size was fixed. $\endgroup$
    – Roman
    Sep 13 '21 at 12:12

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.