Forty years of frequent items

  • Jelani Nelson

    Soda Hall 633, Berkeley, CA, USA 94720-1776
Forty years of frequent items cover
Download Chapter PDF

This book chapter is published open access.


We survey the last 40 years of algorithm development for finding frequent items in data streams, a line of work which surprisingly wound up developing new tools in information theory, pseudorandomness, chaining methods for bounding suprema of stochastic processes, and spectral graph theory.