Alternative Approach for Bloom Filters Folklore Bloom filter construction. ■ Recall:Given a set S={x3...x on a universe U,want to answer membership queries. ■ Method:Find an n-cell perfect hash function for S. Maps set of n elements to n cells in a 1-1 manner. ■ Then keepog2(1/bit fingerprint of item in each cell. Lookups have false positive & ■ Advantage:each bit/item reduces false positives by a factor of 1/2,vs In 2 for a standard Bloom filter. ▣Negatives: Perfect hash functions non-trivial to find. Cannot handle on-line insertions. 1111 Alternative Approach for Bloom Filters  Folklore Bloom filter construction.  Recall: Given a set S = { x1,x 2,x 3,… x n } on a universe U, want to answer membership queries.  Method: Find an n-cell perfect hash function for S.  Maps set of n elements to n cells in a 1-1 manner.  Then keep bit fingerprint of item in each cell. Lookups have false positive < .  Advantage: each bit/item reduces false positives by a factor of 1/2, vs ln 2 for a standard Bloom filter.  Negatives:  Perfect hash functions non-trivial to find.  Cannot handle on-line insertions. log 2 ( 1 /  ) 