@InterfaceAudience.Public
@InterfaceStability.Stable
public class DynamicBloomFilter
extends org.apache.hadoop.util.bloom.Filter
A dynamic Bloom filter (DBF) makes use of a s * m
bit matrix but
each of the s
rows is a standard Bloom filter. The creation
process of a DBF is iterative. At the start, the DBF is a 1 * m
bit matrix, i.e., it is composed of a single standard Bloom filter.
It assumes that nr
elements are recorded in the
initial bit vector, where nr <= n
(n
is the cardinality of the set A
to record in
the filter).
As the size of A
grows during the execution of the application,
several keys must be inserted in the DBF. When inserting a key into the DBF,
one must first get an active Bloom filter in the matrix. A Bloom filter is
active when the number of recorded keys, nr
, is
strictly less than the current cardinality of A
, n
.
If an active Bloom filter is found, the key is inserted and
nr
is incremented by one. On the other hand, if there
is no active Bloom filter, a new one is created (i.e., a new row is added to
the matrix) according to the current size of A
and the element
is added in this new Bloom filter and the nr
value of
this new Bloom filter is set to one. A given key is said to belong to the
DBF if the k
positions are set to one in one of the matrix rows.
Originally created by European Commission One-Lab Project 034819.
The general behavior of a filter
,
A Bloom filter
,
Theory and Network Applications of Dynamic Bloom FiltersConstructor and Description |
---|
DynamicBloomFilter()
Zero-args constructor for the serialization.
|
DynamicBloomFilter(int vectorSize,
int nbHash,
int hashType,
int nr)
Constructor.
|
Modifier and Type | Method and Description |
---|---|
void |
add(org.apache.hadoop.util.bloom.Key key)
Adds a key to this filter.
|
void |
and(org.apache.hadoop.util.bloom.Filter filter)
Peforms a logical AND between this filter and a specified filter.
|
boolean |
membershipTest(org.apache.hadoop.util.bloom.Key key)
Determines wether a specified key belongs to this filter.
|
void |
not()
Performs a logical NOT on this filter.
|
void |
or(org.apache.hadoop.util.bloom.Filter filter)
Peforms a logical OR between this filter and a specified filter.
|
void |
readFields(DataInput in)
Deserialize the fields of this object from
in . |
String |
toString() |
void |
write(DataOutput out)
Serialize the fields of this object to
out . |
void |
xor(org.apache.hadoop.util.bloom.Filter filter)
Peforms a logical XOR between this filter and a specified filter.
|
public DynamicBloomFilter()
public DynamicBloomFilter(int vectorSize, int nbHash, int hashType, int nr)
Builds an empty Dynamic Bloom filter.
vectorSize
- The number of bits in the vector.nbHash
- The number of hash function to consider.hashType
- type of the hashing function (see
Hash
).nr
- The threshold for the maximum number of keys to record in a
dynamic Bloom filter row.public void add(org.apache.hadoop.util.bloom.Key key)
org.apache.hadoop.util.bloom.Filter
add
in class org.apache.hadoop.util.bloom.Filter
key
- The key to add.public void and(org.apache.hadoop.util.bloom.Filter filter)
org.apache.hadoop.util.bloom.Filter
Invariant: The result is assigned to this filter.
and
in class org.apache.hadoop.util.bloom.Filter
filter
- The filter to AND with.public boolean membershipTest(org.apache.hadoop.util.bloom.Key key)
org.apache.hadoop.util.bloom.Filter
membershipTest
in class org.apache.hadoop.util.bloom.Filter
key
- The key to test.public void not()
org.apache.hadoop.util.bloom.Filter
The result is assigned to this filter.
not
in class org.apache.hadoop.util.bloom.Filter
public void or(org.apache.hadoop.util.bloom.Filter filter)
org.apache.hadoop.util.bloom.Filter
Invariant: The result is assigned to this filter.
or
in class org.apache.hadoop.util.bloom.Filter
filter
- The filter to OR with.public void xor(org.apache.hadoop.util.bloom.Filter filter)
org.apache.hadoop.util.bloom.Filter
Invariant: The result is assigned to this filter.
xor
in class org.apache.hadoop.util.bloom.Filter
filter
- The filter to XOR with.public void write(DataOutput out) throws IOException
Writable
out
.write
in interface Writable
write
in class org.apache.hadoop.util.bloom.Filter
out
- DataOuput
to serialize this object into.IOException
- any other problem for write.public void readFields(DataInput in) throws IOException
Writable
in
.
For efficiency, implementations should attempt to re-use storage in the existing object where possible.
readFields
in interface Writable
readFields
in class org.apache.hadoop.util.bloom.Filter
in
- DataInput
to deseriablize this object from.IOException
- any other problem for readFields.Copyright © 2024 Apache Software Foundation. All rights reserved.