@InterfaceAudience.Public @InterfaceStability.Stable public class DynamicBloomFilter extends 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.
hash, hashType, nbHash, vectorSize
Constructor 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(Key key)
Adds a key to this filter.
|
void |
and(Filter filter)
Peforms a logical AND between this filter and a specified filter.
|
boolean |
membershipTest(Key key)
Determines wether a specified key belongs to this filter.
|
void |
not()
Performs a logical NOT on this filter.
|
void |
or(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(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 and(Filter filter)
Filter
Invariant: The result is assigned to this filter.
public boolean membershipTest(Key key)
Filter
membershipTest
in class Filter
key
- The key to test.public void not()
Filter
The result is assigned to this filter.
public void or(Filter filter)
Filter
Invariant: The result is assigned to this filter.
public void xor(Filter filter)
Filter
Invariant: The result is assigned to this filter.
public void write(DataOutput out) throws IOException
Writable
out
.write
in interface Writable
write
in class Filter
out
- DataOuput
to serialize this object into.IOException
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 Filter
in
- DataInput
to deseriablize this object from.IOException
Copyright © 2013 Apache Software Foundation. All rights reserved.