11 votes
Accepted

How to show that the median cannot be maintained in $O(1)$ time?

If you can maintain the median of $n$ objects in $O(1)$, then you can sort a sequence $x_1, \dots, x_n$ in $O(n)$: first you compute a value $a$ smaller than all elements in the sequence and a value $...
user avatar
  • 685
3 votes

Sublinear finite-precision sampling in a stream

The strategy will be to use Vitter's algorithm, but replace the arbitrary-precision random number with online generation of the bits of that random number. Building block: sampling without arbitrary ...
user avatar
  • 10.4k
3 votes

How much memory is needed for counting distinct elements in a stream exactly with high probability

You can do $O(\log \frac n\epsilon)$ space if you only want an approximation. The main idea is that you use the random hash function $h$ to do the same protocol as in the Goldwasser-Sipser Set ...
user avatar
  • 13.5k
2 votes

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 ...
user avatar
2 votes

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 ...
user avatar
  • 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 ...
user avatar
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.
user avatar
  • 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 ...
user avatar
  • 1,412

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