High accuracy bloom filter using partitioned hashing

1. A non-transitory computer readable storage medium including instructions which, when executed by a processor, perform a method comprising:

partitioning into respective groups, each of a plurality of initial keys according to a first hash function, where each group is associated with a respective set of k hash functions, wherein a different set of k hash functions is used for each group, k being an integer greater than zero, said first hash function being different than said k hash functions; and

mapping each hashed key into a bloom filter using the k hash functions associated with its respective group.

2. The method of claim 1 , further comprising:

mapping a newly arrived key to a group according to the first hash function; and

mapping the newly arrived key to the bloom filter using the k hash functions of the mapped to group; wherein

the newly arrived key is deemed to be a member of a set of initial keys only if mapped to set bits in the bloom filter.

3. The method of claim 1 , wherein respective k hash functions associated with groups are selected by iteratively adapting the k hash functions until a fill factor of the bloom filter is below a threshold level.

4. The method of claim 1 , wherein respective k hash functions associated with groups are selected by iteratively adapting the k hash functions until a fill factor of the bloom filter does not decrease between iterations.

5. The method of claim 1 , wherein respective k hash functions associated with groups are selected by iteratively adapting the k hash functions until a fill factor of the bloom filter does not decrease by more than a threshold level.

6. The method of claim 1 , wherein said hash functions comprise random hash functions.

7. The method of claim 1 , wherein said hash functions comprise cyclic redundancy check (CRC) based hash functions.

8. The method of claim 1 , wherein said computer readable medium comprises a memory within a network element adapted to process data streams to determine if the data streams include key terms.

9. A system, comprising:

an input/output circuit adapted to receive data streams;

a memory, for storing computer instructions for a method of processing the received data stream; and

a processor, for executing the computer instructions;

wherein while executing the computer instructions the processor operates to hash received data into respective groups according to a first hash function wherein a different set of k hash functions is used for each group, and to hash each of the groups into a bloom filter according to k respective hash functions, where k is an integer greater than zero, said first hash function being different than said k hash functions; whereby

a matching of received data to a desired search term is indicated when data is hashed into set bits within the bloom filter.

10. The system of claim 9 , wherein the set bits within the bloom filter are initially determined by:

mapping into respective groups each of at least one search terms according to the first hash function, where each group is associated with k hash functions, k being an integer greater than zero; and

mapping each hashed key into a bloom filter using the k hash functions associated with its respective group.

11. The system of claim 10 , wherein respective k hash functions associated with groups are selected by iteratively adapting the k hash functions until a fill factor of the bloom filter is below a threshold level.

12. The system of claim 10 , wherein respective k hash functions associated with groups are selected by iteratively adapting the k hash functions until a fill factor of the bloom filter does not decrease between iterations.

13. The system of claim 10 , wherein respective k hash functions associated with groups are selected by iteratively adapting the k hash functions until a fill factor of the bloom filter does not decrease by more than a threshold level.

14. The system of claim 9 , wherein said hash functions comprise random hash functions.

15. The system of claim 9 , wherein said hash functions comprise cyclic redundancy check (CRC) based hash functions.

16. A computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer to perform a method of processing a received data stream, the method comprising:

hashing received data into respective groups according to a first hash function wherein a different set of k hash functions is used for each group; and

hashing each of the groups into a bloom filter according to k respective hash functions, where k is an integer greater than zero, said first hash function being different than said k hash functions; whereby a matching of received data to a desired search term is indicated when data is hashed into set bits within the bloom filter.

17. Apparatus for processing a received data stream to identify desired search terms, comprising:

means for hashing received data into respective groups according to a first hash function wherein a different set of k hash functions is used for each group; and

means for hashing each of the groups into a bloom filter according to k respective hash functions, where k is an integer greater than zero, said first hash function being different than said k hash functions;

wherein a matching of received data to a desired search term is indicated when data is hashed into set bits within the bloom filter.