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.APPROX-RANDOM.2018.18
URN: urn:nbn:de:0030-drops-94221
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9422/
Go to the corresponding LIPIcs Volume Portal

Li, Yi ; Nakos, Vasileios

Deterministic Heavy Hitters with Sublinear Query Time

pdf-format:
LIPIcs-APPROX-RANDOM-2018-18.pdf (0.5 MB)

Abstract

We study the classic problem of finding l_1 heavy hitters in the streaming model. In the general turnstile model, we give the first deterministic sublinear-time sketching algorithm which takes a linear sketch of length O(epsilon^{-2} log n * log^*(epsilon^{-1})), which is only a factor of log^*(epsilon^{-1}) more than the best existing polynomial-time sketching algorithm (Nelson et al., RANDOM '12). Our approach is based on an iterative procedure, where most unrecovered heavy hitters are identified in each iteration. Although this technique has been extensively employed in the related problem of sparse recovery, this is the first time, to the best of our knowledge, that it has been used in the context of heavy hitters. Along the way we also obtain a sublinear time algorithm for the closely related problem of the l_1/l_1 compressed sensing, matching the space usage of previous (super-)linear time algorithms. In the strict turnstile model, we show that the runtime can be improved and the sketching matrix can be made strongly explicit with O(epsilon^{-2}log^3 n/log^3(1/epsilon)) rows.

BibTeX - Entry

@InProceedings{li_et_al:LIPIcs:2018:9422,
  author =	{Yi Li and Vasileios Nakos},
  title =	{{Deterministic Heavy Hitters with Sublinear Query Time}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9422},
  URN =		{urn:nbn:de:0030-drops-94221},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.18},
  annote =	{Keywords: heavy hitters, turnstile model, sketching algorithm, strongly explicit}
}

Keywords: heavy hitters, turnstile model, sketching algorithm, strongly explicit
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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