This was a variation of the 2011 PFAC talk to introduce Flajolet’s streaming legacy, given at a conference dedicated to bridging the gap between implementers and researchers, organized by Aggregate Knowledge.

As a PhD student at Inria Rocquencourt, I gave a talk that provided an overview of how data streaming algorithms like HyperLogLog work, that was aimed at a broader audience of engineering PhD students at the Inria’s Junior Seminar.

This talk traces the history of data streaming algorithms for the cardinality estimation problem from the 1980s to 2010s through algorithms designed or studied by Philippe Flajolet, and the origins of the world-famous HyperLogLog algorithm.