Approximate membership query structures (e.g. Bloom filters, cuckoo filters, XOR filters, etc.) are designed to store approximations of sets in surprisingly few bits. Today we see how that's possible and pull together a bunch of techniques from elsewhere in the quarter.
Readings
- Burton Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors
- Bin Fan et al. Cuckoo Filter: Practically Better Than Bloom
Links