.TH BLOOMFILTER 2.SH NAMEBloomfilter \- Bloom filters.SH SYNOPSIS.EXinclude "sets.m";include "bloomfilter.m";bloomfilter := load Bloomfilter Bloomfilter->PATH; init:   fn();filter: fn(d: array of byte, logm, k: int): Sets->Set;.EE.SH DESCRIPTIONA Bloom filter is a method of representing a set to support probabilisticmembership queries. It uses independent hash functions of membersof the set to set elements of a bit-vector..I Initshould be called first to initialise the module..I Filterreturns a Set.I srepresenting the Bloom filter for the single-memberset.RI { d }..I Kindependent hash functions are used, each of range.RI "[0, 2^" logm ),to return a Bloom filter.RI 2^ logmbits wide. It is an error if.I logmis less than 3 or greater than 30..PPBloom filters can be combined by set union.The set represented by Bloom filter.I ais not a subset of another.I bif there are any members in.I athat are not in.IR b .Together,.IR logm ,.IR k ,and.IR n(the number of members in the set)determine the.I "false positve" rate(the probability that a membership test will not eliminatea member that is not in fact in the set).The probability of a.I "false positive"is approximately (1-e^(-\fIkn\fP/(2^\fIlogm\fP))^\fIk\fP.For a given false positive rate,.IR f ,a useful formula to determine appropriate parametersis: \fIk\fP=ceil(-log₂(\fIf\fP)),and \fIlogm\fP=ceil(log₂(\fInk\fP))..SH EXAMPLESCreate a 128 bit-wide bloom filter.I frepresenting all the elementsin the string array.IR elems ,with.IR k =6..EX    A, B, None: import Sets;    for(i:=0; i<len elems; i++)        f = f.X(A|B, filter(array of byte elems[i], 7, 6));.EETest whether the string.I sis a member of.IR f .If there were 12 elements in.IR elems ,the probability of a false positive would beapproximately 0.0063..EX    if(filter(array of byte s, 7, 6).X(A&~B, f).eq(None))        sys->print("'%s' might be a member of f\\n", s);.EE.SH SOURCE.B /appl/lib/bloomfilter.b.SH SEE ALSO.IR sets (2)