5 years ago

# High Probability Frequency Moment Sketches.

David P. Woodruff, Sumit Ganguly

We consider the problem of sketching the $p$-th frequency moment of a vector, $p>2$, with multiplicative error at most $1\pm \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.

Publisher URL: http://arxiv.org/abs/1805.10885

DOI: arXiv:1805.10885v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

Researcher displays publicly available abstracts and doesnâ€™t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.