HIGH ACCURACY BLOOM FILTER USING PARTITIONED HASHING

• US 20080313132A1
• Filed: 06/15/2007
• Published: 12/18/2008
• 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.
• Granted Patent: US 7,930,547 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• 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 computer readable medium including instructions which, when executed by a processor, perform a method comprising:

mapping into respective groups each of a plurality of initial keys according to a 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.

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 said first hash function is different than said k hash functions.

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 is below a threshold level.

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 between iterations.

6. 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.

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

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

9. 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.

10. 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 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;

whereby

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

11. The system of claim 10, 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.

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

13. The system of claim 11, 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.

14. The system of claim 11, 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.

15. The system of claim 10, wherein said hash functions comprise random hash functions.

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

17. 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; and

hashing each of the groups into a bloom filter according to k respective hash functions, where k is an integer greater than zero;

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

18. 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; 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;

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