# Tag Info

Accepted

• 13.5k

### Algorithm for finding heavy hitters in a weighted stream

If you allow randomization, the CountMin (CM) sketch can be used with weights without modification, and can also handle negative weights. When all weights are positive, the standard analysis of CM ...

### Algorithm for finding heavy hitters in a weighted stream

Here's a generic randomized solution. (Do we even have deterministic solutions in the unweighted case? Don't Space Saving and Batch Decrement both need hash maps?) This is probably not the ideal ...
• 2,743
1 vote

### Finding top-K items in a sliding window

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 ...
• 2,186
1 vote
Accepted

### Single-pass streaming quantile estimation using moments

Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.
• 11k
1 vote
Accepted

### Are the ArrowApply and Monad typeclasses equivalent?

The problem with your counterexample is that the type you presented is not a valid instance of ArrowApply as far as I can tell. You didn't present what the ...
• 1,412

Only top scored, non community-wiki answers of a minimum length are eligible