<p>Gan et al. address this in <a href="https://arxiv.org/pdf/1803.01969.pdf" rel="nofollow noreferrer">Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries</a>. The answers are rather nuanced.</p>

CC BY-SA 4.0
2019-10-26T19:31:10.103Z
2019-10-26T19:31:10.103Z
jbapple
<p>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?</p>

<p>By "estimate the quantiles", I mean:</p>

<blockquote>
  <p>... 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]$.</p>
</blockquote>

<p>following <a href="http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf" rel="noreferrer">"Space-Efficient Online Computation of Quantile
Summaries", by Greenwald and Khanna</a>.</p>

<p>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.</p>

<p>I am more interested in deterministic algorithms than randomized ones.</p>

CC BY-SA 3.0
2015-08-19T08:22:21.093Z
Yes. It was $N$ in the paper cited. Fixed.
jbapple
CC BY-SA 3.0
2015-08-19T08:24:51.157Z
Do you have a function $f$ that always suffices?  Does it not have to depend on $\epsilon$?
András Salamon
CC BY-SA 3.0
2015-08-19T08:28:09.243Z
$f(n) = n$ is sufficient, I believe, by https://cstheory.stackexchange.com/questions/27952/solving-a-system-of-sums-of-powers-polynomials
jbapple
CC BY-SA 3.0
2015-08-19T08:37:19.727Z
And yes, presumably it will depend on $\epsilon$.
jbapple
CC BY-SA 3.0
2015-08-19T16:27:57.377Z
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.
<ds.algorithms><data-streams><streaming-algorithms><streaming>
Single-pass streaming quantile estimation using moments
jbapple
# Single-pass streaming quantile estimation using moments

(Asked by: username_0 on 2015-08-19)

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](http://infolab.stanford.edu/~datar/courses/cs361a/papers/quantiles.pdf).

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.

**Tags:** ds.algorithms, data-streams, streaming-algorithms, streaming

> **Comments:**
> **username_0**: Yes. It was $N$ in the paper cited. Fixed.  
> **username_1**: Do you have a function $f$ that always suffices?  Does it not have to depend on $\epsilon$?  
> **username_0**: $f(n) = n$ is sufficient, I believe, by https://cstheory.stackexchange.com/questions/27952/solving-a-system-of-sums-of-powers-polynomials  
> **username_0**: And yes, presumably it will depend on $\epsilon$.  
> **username_2**: 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$.  

---

## 1 answers

### Answer by username_0 on 2019-10-26. Score: 1 | Accepted answer

Gan et al. address this in [Moment-Based Quantile Sketches for Efficient High Cardinality Aggregation Queries](https://arxiv.org/pdf/1803.01969.pdf). The answers are rather nuanced.


---

