Bloom filter with memory element

Abstract

Techniques are provided for determining if an element is contained in a set of elements. In one aspect, an element may be received and inserted into a bloom filter. The element may also be inserted into a memory associative on the bloom filter indexes. In another aspect, a search element may be received and compared to a bloom filter. If the search element is included in the bloom filter, a memory may be used to determine if the search element is included in the set of elements.

1 . A method comprising:
 receiving an element to be included in a set of elements;   computing a plurality of bloom filter indexes based on the element;   inserting the element into a plurality of bloom filters using the plurality of bloom filter indexes; and   storing the element in a memory, wherein the element is accessed in the memory to eliminate false positives.   
     
     
         2 . The method of  claim 1  wherein the plurality of bloom filter indexes is an ordered set of indexes. 
     
     
         3 . The method of  claim 2  wherein storing the element in the memory further comprises:
 locating an empty entry in the memory, wherein at least a portion of the entry is a content addressable memory; 
 storing the ordered set of bloom filter indexes in the content addressable memory portion of the located entry; and 
 storing the element associated with the located entry. 
 
     
     
         4 . The method of  claim 2  wherein storing the element in the memory further comprises:
 locating an empty entry in the memory, wherein at least a portion of the entry is a content addressable memory; and 
 storing the element in the content addressable memory portion of the located entry. 
 
     
     
         5 . The method of  claim 2  wherein storing the element in the memory further comprises:
 computing a hash of the ordered set of indexes; 
 identifying the memory associated with the hash; and 
 adding the element to the identified memory. 
 
     
     
         6 .- 15 . (canceled)