# Single-pass streaming quantile estimation using moments

Is it possible to estimate within $\epsilon$ the quantiles of a set of integers $\{x_1, x_2, \dots, x_n\}$ given only the values $\sum x_i^0,\sum x_i^1, \sum x_i^2, \dots, \sum x_i^{f(n)}$ where $f \in o(n)$? If so, what is the most slowly growing $f$ that will suffice?

By "estimate the quantiles", I mean:

... for any given rank $r$, an $\epsilon$-approximate quantile summary returns a value whose rank $r'$ is guaranteed to be within the interval $[r - \epsilon n, r + \epsilon n]$.

I'm also interested in whether this is possible with non-integer, non-consecutive moments, so sets of values like $\sum x_i^{-1/2}, \sum x_i^\pi$ are also of interest.

I am more interested in deterministic algorithms than randomized ones.

• Yes. It was $N$ in the paper cited. Fixed. Aug 19 '15 at 8:22
• Do you have a function $f$ that always suffices? Does it not have to depend on $\epsilon$? Aug 19 '15 at 8:24
• $f(n) = n$ is sufficient, I believe, by cstheory.stackexchange.com/questions/27952/… Aug 19 '15 at 8:28
• And yes, presumably it will depend on $\epsilon$. Aug 19 '15 at 8:37
• I'm skeptical that any $f=o(n)$ will suffice. Consider estimating the median. For $f=1$, compare the sequence $0,0,0,\dots,0,x$ to $y,\dots,y$ where $y=x/n$; they're indistinguishable from the values you're given, but have very different medians. For $f=2$, compare the sequence $0,0,0,\dots,0,x$ to $y,y,\dots,y,z$ where $x=ny/2$ and $z=-ny/2$; the same thing happens. I suspect this will generalize to larger $f$.
– D.W.
Aug 19 '15 at 16:27