BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Beating CountSketch for Heavy Hitters in Insertion Streams
DTSTART:20160229T161500
DTEND:20160229T171500
DTSTAMP:20260407T063921Z
UID:2c17d06353ea7ec014834dbc724dfe7dae5d52be9bcf8b7b19d04ca5
CATEGORIES:Conferences - Seminars
DESCRIPTION:David P. Woodruff\nAbstract:\nWe consider the problem of findi
 ng the most frequent items in a stream of items from a universe of size n.
  Namely\, we consider returning all l_2-heavy hitters\, i.e.\, those items
  j for which f_j >= eps sqrt{F_2}\, where f_j is the number of occurrences
  of item j\, and F_2 = sum_i f_i^2 is the second moment of the stream. In 
 2002\, Charikar\, Chen\, and Farach-Colton suggested the CountSketch data 
 structure\, which solves this using log^2 n bits of space (for constant ep
 s). The only known lower bound is log n bits. Using Gaussian processes\, w
 e show it is possible to achieve O(log n log log n) bits of space.\nBio:\n
 David Woodruff has been a research scientist in the principles and methodo
 logies group at IBM Almaden since 2007\, which he joined after completing 
 his Ph.D. in theoretical computer science at MIT. His interests are in dat
 a streams\, distributed computation\, machine learning\, and numerical lin
 ear algebra\, among other things. He received the EATCS Presburger Award i
 n 2014\, and Best Paper Awards in STOC 2013 and PODS 2010. He is a member 
 of the IBM Academy of Technology and a Master Inventor at IBM.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR