Suggested Final Project Topics

Bloomier Filters

A Bloomier filter is based on the following, seemingly improbable idea: can you use a Bloom filter, which

is used to approximately encode a set, to approximately encode a map? Amazingly, using random graph

theory and a clever use of the XOR operator, it’s possible to do this in a way where “false lookups” are

comparably rare and the memory usage is kept to a minimum.

Why they’re worth studying: On a theoretical level, Bloomier filters are a fascinating data structure. The

main underlying idea is to use XORs in a way that makes it highly unlikely that missing keys will get an

associated value, but which makes present keys uniquely map to a specific value. On a practical level,

Bloomier filters have recently gotten popular in the compression of deep neural networks, where they rep-

resent a way to (noisly) encode weights between layers in very few bits.