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.ICDT.2016.4
URN: urn:nbn:de:0030-drops-57739
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5773/
Go to the corresponding LIPIcs Volume Portal

Woodruff, David P.

New Algorithms for Heavy Hitters in Data Streams (Invited Talk)

pdf-format:
3.pdf (0.4 MB)

Abstract

An old and fundamental problem in databases and data streams is that of finding the heavy hitters, also known as the top-k, most popular items, frequent items, elephants, or iceberg queries. There are several variants of this problem, which quantify what it means for an item to be frequent, including what are known as the l_1-heavy hitters and l_2-heavy hitters. There are a number of algorithmic solutions for these problems, starting with the work of Misra and Gries, as well as the CountMin and CountSketch data structures, among others.

In this paper (accompanying an invited talk) we cover several recent results developed in this area, which improve upon the classical solutions to these problems. In particular, we develop new algorithms for finding l_1-heavy hitters and l_2-heavy hitters, with significantly less memory required than what was known, and which are optimal in a number of parameter regimes.

BibTeX - Entry

@InProceedings{woodruff:LIPIcs:2016:5773,
  author =	{David P. Woodruff},
  title =	{{New Algorithms for Heavy Hitters in Data Streams (Invited Talk)}},
  booktitle =	{19th International Conference on Database Theory (ICDT 2016)},
  pages =	{4:1--4:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-002-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{48},
  editor =	{Wim Martens and Thomas Zeume},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5773},
  URN =		{urn:nbn:de:0030-drops-57739},
  doi =		{10.4230/LIPIcs.ICDT.2016.4},
  annote =	{Keywords: data streams, heavy hitters}
}

Keywords: data streams, heavy hitters
Collection: 19th International Conference on Database Theory (ICDT 2016)
Issue Date: 2016
Date of publication: 14.03.2016

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