Patent ID: 8209368

Claim:
A method of generating and using a dynamic Bloom filter that includes a plurality of Bloom filters implemented with a processor that includes a memory, comprising: allocating a memory for a first Bloom filter based upon a cardinality estimate, wherein the cardinality is a number of distinct values for a multi-set; receiving an input item into the first Bloom filter, wherein the input item is the multi-set; for the input item into the first Bloom filter, determining a number bits to be set for the input item based on a false positive rate of the first Bloom filter; determining whether the first Bloom filter is at capacity; upon determination that the first Bloom filter is at capacity, allocating a second Bloom filter; upon determination that the first Bloom filter is not at capacity checking if the input item was encoded in a third Bloom filter; upon determination that the input item was previously encoded in the third Bloom filter, proceeding to a next item; and upon determination that the input item was not previously encoded in the third Bloom filter, inserting the input item in the first Bloom filter to generate the dynamic Bloom filter.