Bloom Filters (Cont.) Key idea of Bloom filter:reduce false positives by use multiple hash functions h()for i=1..k For each element s in set S for each i compute hi(s)and set bit hi(s) To query an element v for each i compute hi(v),and check if bit hi(v)is set If bit hi(v)is set for every i then report v as present in set Else report v as absent With 10n bits,and k =7,false positive rate reduces to 1%instead of 10%with k=1 Database System Concepts-7th Edition 24.3 @Silberschatz,Korth and SudarshanDatabase System Concepts - 7 24.3 ©Silberschatz, Korth and Sudarshan th Edition Bloom Filters (Cont.) ▪ Key idea of Bloom filter: reduce false positives by use multiple hash functions hi () for i = 1..k • For each element s in set S for each i compute hi (s) and set bit hi (s) • To query an element v for each i compute hi (v), and check if bit hi (v) is set ▪ If bit hi (v) is set for every i then report v as present in set ▪ Else report v as absent • With 10n bits, and k = 7, false positive rate reduces to 1% instead of 10% with k = 1