Patent ID: 8032529
Filing Date: 2011-10-04
Classification: G06F

Abstract:
1. An apparatus, comprising: an interface configured to receive an element for deletion from a bloom filter, the bloom filter including a plurality of hash functions and an array; a processor configured to generate a plurality of hash function output values for the element using the plurality of hash functions, the plurality of hash function output values corresponding to a plurality of indices identifying a plurality of entries in the array, each of the plurality of entries comprising one or more bits; a memory configured to maintain a plurality of supplemental data structure entries in a supplemental data structure, the supplemental data structure configured to maintain supplemental data structure entries only for saturated entries in the array associated with the bloom filter, the plurality of supplemental data structure entries associated with the plurality of indices; wherein a first subset of the plurality of entries in the array are saturated and a second subset of the plurality of entries in the array are clear, and wherein the second subset of the plurality of entries do not have supplemental data structure entries; wherein the processor is configured to modify-the plurality of supplemental data structure entries to delete the element from the bloom filter.