Bloom Filters and MinHash: Two Probabilistic Data Structures

Abstract: Seemingly simple operations on sets, such as membership checking and comparison, can become time or space prohibitive when the sets are very large. In this lecture, I will demonstrate how leveraging uncertainty can improve these operations on large sets. I will first cover Bloom filters, which can store members of a set using just a few bits per item and check set membership in a fraction of the time required to search a list. Next, I will discuss MinHash, a method that represents a set with a randomly chosen element for more efficient set comparison.

Biosketch: Kel Levick is a PhD candidate in Electrical and Computer Engineering at the University of Illinois Urbana-Champaign, advised by Dr. Ilan Shomorony. Her research uses computational methods to identify genes of interest and their genomic context from metagenomic samples. She has earned several graduate teaching awards, including an ECE Department Fellowship and a Future Faculty Fellowship.