Name
Abstract | ||
|---|---|---|
We consider the problem of sketching the $p$-th frequency moment of a vector, $pu003e2$, with multiplicative error at most $1pm epsilon$ and emph{with high confidence} $1-delta$. Despite the long sequence of work on this problem, tight bounds on this quantity are only known for constant $delta$. While one can obtain an upper bound with error probability $delta$ by repeating a sketching algorithm with constant error probability $O(log(1/delta))$ times in parallel, and taking the median of the outputs, we show this is a suboptimal algorithm! Namely, we show optimal upper and lower bounds of $Theta(n^{1-2/p} log(1/delta) + n^{1-2/p} log^{2/p} (1/delta) log n)$ on the sketching dimension, for any constant approximation. Our result should be contrasted with results for estimating frequency moments for $1 leq p leq 2$, for which we show the optimal algorithm for general $delta$ is obtained by repeating the optimal algorithm for constant error probability $O(log(1/delta))$ times and taking the median output. We also obtain a matching lower bound for this problem, up to constant factors. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.ICALP.2018.58 | ICALP |
DocType | Volume | Citations |
Conference | abs/1805.10885 | 0 |
PageRank | References | Authors |
0.34 | 18 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sumit Ganguly | 1 | 813 | 236.01 |
| David P. Woodruff | 2 | 2156 | 142.38 |