<p>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 <em>ad hoc</em> windows in a data stream. In particular:</p>
<ul>
<li><p>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;</p>
</li>
<li><p>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;</p>
</li>
<li><p>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.</p>
</li>
</ul>
<p>The algorithms are described in the following <a href="https://helios2.mi.parisdescartes.fr/%7Ethemisp/adhocfrequentitems/" rel="nofollow noreferrer">paper</a>:</p>
<p>Michele Dallachiesa and Themis Palpanas. 2013. Identifying streaming frequent items in ad hoc time windows. Data Knowl. Eng. 87 (September, 2013), 66–90. DOI:<a href="https://doi.org/10.1016/j.datak.2013.05.007" rel="nofollow noreferrer">https://doi.org/10.1016/j.datak.2013.05.007</a></p>
<p>The paper can be found <a href="https://helios2.mi.parisdescartes.fr/%7Ethemisp/adhocfrequentitems/dke13-frequentitems.pdf" rel="nofollow noreferrer">here</a>; the source code is also available <a href="https://helios2.mi.parisdescartes.fr/%7Ethemisp/adhocfrequentitems/sourcecode.zip" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2022-02-11T18:09:10.640Z
2022-02-11T18:09:10.640Z
Massimo Cafaro
<p>There probably are better ways but here goes.</p>
<p>Let each transaction be denoted <span class="math-container">$(i,A_i)$</span> and let them arrive in a stream.</p>
<p>Initialize a list <span class="math-container">$L:=[]$</span> which will be sorted on the second component.</p>
<p>For the first <span class="math-container">$K$</span> transactions insert <span class="math-container">$(i,A_i)$</span> into the proper position in <span class="math-container">$L.$</span> Let <span class="math-container">$L[1]$</span> denote the smallest entry in <span class="math-container">$L.$</span></p>
<p>Since the maximum amount seen so far is monotone increasing, if the next seen transaction <span class="math-container">$(i,A_i)$</span> satisfies <span class="math-container">$A_i\geq A_j$</span> for all <span class="math-container">$(j,A_j)$</span> in <span class="math-container">$L$</span>  discard <span class="math-container">$L[1]$</span> from the list and then insert <span class="math-container">$(i,A_j)$</span> into its proper place in the list.</p>
<p>If there is a tie with <span class="math-container">$L[1]$</span> you can break ties arbitrarily if you wish to avoid the property that the latest <span class="math-container">$K^{th}$</span> largest transaction will end up in the list.</p>

CC BY-SA 4.0
2021-08-31T21:34:22.010Z
2021-08-31T21:34:22.010Z
kodlu
<p>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.</p>
<p>Are there any algorithms/papers that address this kind of problem?</p>
<p>Few clarifications:</p>
<ol>
<li>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 &quot;Top-K most frequent items&quot;.</li>
<li>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).</li>
</ol>

CC BY-SA 4.0
2021-09-01T19:01:16.937Z
What did you try? Where did you get stuck? What's the best known bound for similar problems that you've looked up?
jbapple
CC BY-SA 4.0
2021-09-13T12:12:39.980Z
@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.
Roman
<approximation-algorithms><sorting><data-streams><streaming-algorithms>
Finding top-K items in a sliding window
Roman
# Finding top-K items in a sliding window

(Asked by: username_0 on 2021-08-26)

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).

**Tags:** approximation-algorithms, sorting, data-streams, streaming-algorithms

> **Comments:**
> **username_1**: What did you try? Where did you get stuck? What's the best known bound for similar problems that you've looked up?  
> **username_0**: @username_1 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.  

---

## 2 answers

### Answer by username_2 on 2022-02-11. Score: 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](https://helios2.mi.parisdescartes.fr/%7Ethemisp/adhocfrequentitems/):

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](https://helios2.mi.parisdescartes.fr/%7Ethemisp/adhocfrequentitems/dke13-frequentitems.pdf); the source code is also available [here](https://helios2.mi.parisdescartes.fr/%7Ethemisp/adhocfrequentitems/sourcecode.zip).


---

### Answer by username_3 on 2021-08-31. Score: 0

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.


---

