11 votes

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 $...
Louis's user avatar
  • 775
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 ...
D.W.'s user avatar
  • 11.7k
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 ...
domotorp's user avatar
  • 13.9k
3 votes

Boosting the probability of success(random projections, johnson lindenstrauss)

If the probability of success of an event is $1/n$, then the failure probability is $(1 - 1/n)$. Hence the probability of failure for $n$ independent trials is $(1 - 1/n)^n$. The limit as $n$ goes to ...
Sid Jain's user avatar
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 ...
Massimo Cafaro's user avatar
1 vote

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.
jbapple's user avatar
  • 11.2k
1 vote

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 ...
Max New's user avatar
  • 1,653

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