Probabilistic methods for large sets

Large sets appear in many contexts in data science. We're likely to encounter them while dealing with users' implicit feedback as previously mentioned, but the approaches described next can be applied to any data that can be represented as a set.

Testing set membership with Bloom filters

Bloom filters are data structures that provide a means to compress the size of a set while preserving our ability to tell whether a given item is a member of the set or not. The price of this compression is some uncertainty. A Bloom filter tells us when an item may be in a set, although it will tell us for certain if it isn't. In situations where disk space saving is worth the small sacrifice in certainty, they are a very popular choice for set compression.

The base data structure of a Bloom filter is a bit vector—a sequence of cells that may contain 1 or 0 (or true or false). The level of compression (and the corresponding increase in uncertainty...