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 $...
- 820
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 ...
- 31
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 ...
- 12.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 ...
- 14.2k
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,216
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.
- 11.2k
Only top scored, non community-wiki answers of a minimum length are eligible