New Algorithms for Heavy Hitters in Data Streams 1/2
216 views · Published 28 March 2016 · 50:07 · Indexed 19 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By David Woodruff (IBM Almaden) 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 ℓ1-heavy hitters and ℓ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 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 ℓ1 - heavy hitters and ℓ2-heavy hitters, with significantly less memory required than what was known, and which are optimal in a number of parameter regimes.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...