Built on
sketch
Articles
DS
Data structure
Bloom filter
Says “surely not” or “maybe yes” about set membership, at about 10 bits per item.
O(k)
2 problems
SYS
Data structure
Count-Min Sketch
Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards.
O(d) per item and per query
2 problems
Problems
Often together
probabilistic 2 hashing 2 in production 2 membership 1 bitset 1 databases 1 security 1 interviews 1 frequencies 1 streaming 1 networks 1 analytics 1