5
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ Yes. It was $N$ in the paper cited. Fixed. $\endgroup$
    – jbapple
    Aug 19, 2015 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, 2015 at 8:24
  • 1
    $\begingroup$ $f(n) = n$ is sufficient, I believe, by cstheory.stackexchange.com/questions/27952/… $\endgroup$
    – jbapple
    Aug 19, 2015 at 8:28
  • $\begingroup$ And yes, presumably it will depend on $\epsilon$. $\endgroup$
    – jbapple
    Aug 19, 2015 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, 2015 at 16:27

1 Answer 1

Reset to default
1
$\begingroup$

Gan et al. address this in Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries. The answers are rather nuanced.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.