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]$.

following "Space-Efficient Online Computation of Quantile Summaries", by Greenwald and Khanna.

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.

  • $\begingroup$ Yes. It was $N$ in the paper cited. Fixed. $\endgroup$ – jbapple Aug 19 '15 at 8:22
  • $\begingroup$ Do you have a function $f$ that always suffices? Does it not have to depend on $\epsilon$? $\endgroup$ – András Salamon Aug 19 '15 at 8:24
  • 1
    $\begingroup$ $f(n) = n$ is sufficient, I believe, by cstheory.stackexchange.com/questions/27952/… $\endgroup$ – jbapple Aug 19 '15 at 8:28
  • $\begingroup$ And yes, presumably it will depend on $\epsilon$. $\endgroup$ – jbapple Aug 19 '15 at 8:37
  • 1
    $\begingroup$ 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$. $\endgroup$ – D.W. Aug 19 '15 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.