Classic Uses of BF:Spell-Checking Once upon a time,memory was scarce... /usr/dict/words -about 210KB,25K words ▣Use25 KB Bloom filter ■8 bits per word. Optimal 5 hash functions. Probability of false positive about 2% False positive accept a misspelled word BFs still used to deal with list of words Password security [Spafford 1992],[Manber Wu,94] Keyword driven ads in web search engines,etc 1313 Classic Uses of BF: Spell-Checking Once upon a time, memory was scarce... /usr/dict/words -- about 210KB, 25K words Use 25 KB Bloom filter 8 bits per word. Optimal 5 hash functions. Probability of false positive about 2% False positive = accept a misspelled word BFs still used to deal with list of words Password security [Spafford 1992], [Manber & Wu, 94] Keyword driven ads in web search engines, etc