Patent ID: 7937428

Claim:
A method of implementing a dynamic Bloom filter comprised of one or more filters, the method comprising: generating the dynamic Bloom filter according to the following steps: initializing a filter counter to zero; setting a filter capacity indicator to a value of true; while an input item is available, if the filter capacity indicator is true then, incrementing the filter counter by one; allocating a memory for a current filter based upon a cardinality estimate and a false positive rate; determining a number of bits to be set for the input item based upon the false positive rate for the current filter; and inserting the input item into the current filter; otherwise, checking a first selected filter to determine if the input item is contained therein; ignoring the input item if the input item is found in the first selected filter; inserting the input item into the current filter if the input item was not found in any selected filter; and setting the filter capacity indicator to true if the item is inserted in the current filter and current filter is at capacity thereafter; and using the dynamic Bloom filter according to the following steps: receiving a query for an item; applying the query to a second selected filter in the dynamic Bloom filter; upon determination that the query of the second selected filter returns a positive a positive result, returning the positive result for the query; and returning a negative result for the query of the dynamic Bloom filter if no selected filter returns a positive result.