Suggested Final Project Topics

If You’re Interested in Randomized Data Structures, Check Out...

The HyperLogLog Estimator

The HyperLogLog estimator is a data structure for estimating how many unique elements exist in a data

stream. Impressively, it can get a high-quality estimate using an extremely small number of total bits,

making it a popular choice in database implementations and data centers.

Why they're worth studying:  Cardinality estimators have a long history and are used extensively in

database systems to determine which of several different algorithms should be used when performing op-

erations on huge data sets. Additionally, the mathematical analyses involved in cardinality estimators are

quite clever and will give you a sense of how nontrivial the analysis of a randomized data structure can be.

A Caveat: The math behind the HyperLogLog data structure is fairly challenging and technical. We’re

confident that a hardworking team could find a way to simplify the presentation or at least make it more

intuitive, and we’d be extremely grateful to any team that manages to do this!