3.7 Probabilistic Data Structures
Bloom filters, cuckoo filters, count-min sketch, HyperLogLog, MinHash, reservoir sampling, skip lists, and treaps as probabilistic structures.
Tag
Probabilistic
3 notes
3 notes
Bloom filters, cuckoo filters, count-min sketch, HyperLogLog, MinHash, reservoir sampling, skip lists, and treaps as probabilistic structures.
Approximate frequency counting for large key streams using a compact probabilistic data structure with bounded error.
Test set membership approximately using a compact bit array and multiple hash functions, with no false negatives and bounded false positives.