Citrix Systems, Inc.
GENERATION AND USE OF A DYNAMIC BLOOM FILTER

Abstract:

An example methodology includes generating a dynamic Bloom filter. The dynamic Bloom filter may be generated based on a target false positive rate, a total number of elements to be inserted within a data structure of the dynamic Bloom filter, and at least one hash function. The total number of elements correspond to the number of first elements encoded in a data structure of an existing Bloom filter and a number of second elements to be added to the existing Bloom filter. The first elements may be inserted into the data structure of the dynamic Bloom filter by translating indexes with a bit having a first value in the data structure of the existing Bloom filter to the data structure of the dynamic Bloom filter. The second elements may be inserted into the data structure of the dynamic Bloom filter based on corresponding hash values.