High accuracy bloom filter using partitioned hashing
AssigneeAlcatel-Lucent USA Inc.
InventorsFang Hao, Muralidharan Sampath Kodialam, Tirunell V. Lakshman
Life of this patent
Estimating the term…
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.
Claims17
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.
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.
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.
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.
Dependencies are inferred from the claim text.