|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object org.apache.hadoop.util.bloom.Filter org.apache.hadoop.util.bloom.BloomFilter org.apache.hadoop.util.bloom.RetouchedBloomFilter
public final class RetouchedBloomFilter
Implements a retouched Bloom filter, as defined in the CoNEXT 2006 paper.
It allows the removal of selected false positives at the cost of introducing random false negatives, and with the benefit of eliminating some random false positives at the same time.
Originally created by European Commission One-Lab Project 034819.
The general behavior of a filter
,
A Bloom filter
,
The different selective clearing algorithms
,
Retouched Bloom Filters: Allowing Networked Applications to Trade Off Selected False Positives Against False NegativesField Summary |
---|
Fields inherited from class org.apache.hadoop.util.bloom.Filter |
---|
hash, hashType, nbHash, vectorSize |
Fields inherited from interface org.apache.hadoop.util.bloom.RemoveScheme |
---|
MAXIMUM_FP, MINIMUM_FN, RANDOM, RATIO |
Constructor Summary | |
---|---|
RetouchedBloomFilter()
Default constructor - use with readFields |
|
RetouchedBloomFilter(int vectorSize,
int nbHash,
int hashType)
Constructor |
Method Summary | |
---|---|
void |
add(Key key)
Adds a key to this filter. |
void |
addFalsePositive(Collection<Key> coll)
Adds a collection of false positive information to this retouched Bloom filter. |
void |
addFalsePositive(Key key)
Adds a false positive information to this retouched Bloom filter. |
void |
addFalsePositive(Key[] keys)
Adds an array of false positive information to this retouched Bloom filter. |
void |
addFalsePositive(List<Key> keys)
Adds a list of false positive information to this retouched Bloom filter. |
void |
readFields(DataInput in)
Deserialize the fields of this object from in . |
void |
selectiveClearing(Key k,
short scheme)
Performs the selective clearing for a given key. |
void |
write(DataOutput out)
Serialize the fields of this object to out . |
Methods inherited from class org.apache.hadoop.util.bloom.BloomFilter |
---|
and, getVectorSize, membershipTest, not, or, toString, xor |
Methods inherited from class org.apache.hadoop.util.bloom.Filter |
---|
add, add, add |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public RetouchedBloomFilter()
public RetouchedBloomFilter(int vectorSize, int nbHash, int hashType)
vectorSize
- The vector size of this filter.nbHash
- The number of hash function to consider.hashType
- type of the hashing function (see
Hash
).Method Detail |
---|
public void add(Key key)
Filter
add
in class BloomFilter
key
- The key to add.public void addFalsePositive(Key key)
Invariant: if the false positive is null
, nothing happens.
key
- The false positive key to add.public void addFalsePositive(Collection<Key> coll)
coll
- The collection of false positive.public void addFalsePositive(List<Key> keys)
keys
- The list of false positive.public void addFalsePositive(Key[] keys)
keys
- The array of false positive.public void selectiveClearing(Key k, short scheme)
k
- The false positive key to remove from this retouched Bloom filter.scheme
- The selective clearing scheme to apply.public void write(DataOutput out) throws IOException
Writable
out
.
write
in interface Writable
write
in class BloomFilter
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 BloomFilter
in
- DataInput
to deseriablize this object from.
IOException
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |