High accuracy bloom filter using partitioned hashing

• US 7,930,547 B2
• Filed: 06/15/2007
• Issued: 04/19/2011
• Est. Priority Date: 06/15/2007
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Hao, Fang, Kodialam, Muralidharan Sampath, Lakshman, Tirunell V.
• Primary Examiner(s): Hoffman; Brandon S
• Application Number:
  US11/763,676
• Publication Number:
  US 20080313132A1
• Time in Patent Office: 1,404 Days
• Field of Search: None
• US Class Current: 713/176
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 45/7459 using Bloom filters

Abstract

A method and system for generating a bloom filter by mapping into respective groups each of a plurality of initial keys according to a first hash function and mapping each group hashed key into a bloom filter using k respective hash functions.

Claims

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.