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 $...
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.
Only top scored, non community-wiki answers of a minimum length are eligible
Related Tags
streaming × 13ds.algorithms × 7
data-streams × 7
lower-bounds × 4
communication-complexity × 4
streaming-algorithms × 4
cc.complexity-theory × 2
derandomization × 2
co.combinatorics × 1
automata-theory × 1
ds.data-structures × 1
randomized-algorithms × 1
regular-language × 1
st.statistics × 1
survey × 1
pseudorandom-generators × 1
monad × 1
sliding-window × 1