Method and apparatus for multiset membership testing using combinatorial bloom filters
AssigneeAlcatel Lucent
InventorsFang Hao, Muralidharan Sampath Kodialam, Tirunell V. Lakshman, Haoyu Song
Life of this patent
Estimating the term…
Abstract
A method and apparatus providing improved set membership determination and group membership identification of candidate data elements using a single Bloom filter programmed to provide a plurality of non-zero f-bit binary vectors, where each of the f-bit binary vectors is associated with a respective group. The Bloom filter is programmed using one or more (but not all) of a plurality of hash filter sets.
Claims21
A method for identifying group membership of a candidate data element in a data processing apparatus including at least a memory circuit, the method comprising:
- providing in the memory circuit a plurality of hash sets operative to program a single Bloom filter with a plurality of non-zero f-bit binary vectors, each of the f-bit binary vectors being associated with a respective group indicative of group IDs for one or more candidate data elements;
- performing group membership probes into the Bloom filter using candidate data elements to generate thereby f-bit binary vector output signal indicative of a matching function.
An apparatus for identifying group membership of a candidate data element, comprising:
- a first memory, for storing a plurality of hash sets operative to program a single Bloom filter with a plurality of non-zero f-bit binary vectors, each of the f-bit binary vectors being associated with a respective group indicative of group IDs for one or more candidate data elements;
- and
- a second memory, for storing f sets of h hashing functions;
- wherein group membership probes into the Bloom filter are performed by hashing candidate data elements according to each of the h hashing functions of each of the f sets of hashing functions.
A computer-readable non-transitory medium storing a software program, that, when executed by a computer, causes the computer to perform a method for identifying group membership of a candidate data element, the method comprising:
- providing in the memory circuit a plurality of hash sets operative to program a single Bloom filter with a plurality of non-zero f-bit binary vectors, each of the f-bit binary vectors being associated with a respective group indicative of group IDs for one or more candidate data elements;
- performing group membership probes into the Bloom filter using candidate data elements.
Dependencies are inferred from the claim text.