Bloom Filter

A Bloom filter checks whether something belongs to a set without storing the set. Firefox’s CRLite used one to compress revocation data for nearly a billion certificates into 6.7 megabytes.