License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.58
URN: urn:nbn:de:0030-drops-90623
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9062/
Go to the corresponding LIPIcs Volume Portal

Ganguly, Sumit ; Woodruff, David P.

High Probability Frequency Moment Sketches

pdf-format:
LIPIcs-ICALP-2018-58.pdf (0.7 MB)

Abstract

We consider the problem of sketching the p-th frequency moment of a vector, p>2, with multiplicative error at most 1 +/- epsilon and 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 <= p <= 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.

BibTeX - Entry

@InProceedings{ganguly_et_al:LIPIcs:2018:9062,
  author =	{Sumit Ganguly and David P. Woodruff},
  title =	{{High Probability Frequency Moment Sketches}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9062},
  URN =		{urn:nbn:de:0030-drops-90623},
  doi =		{10.4230/LIPIcs.ICALP.2018.58},
  annote =	{Keywords: Data Streams, Frequency Moments, High Confidence}
}

Keywords: Data Streams, Frequency Moments, High Confidence
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI