org.apache.hadoop.util.bloom

Class RetouchedBloomFilter

java.lang.Object

org.apache.hadoop.util.bloom.Filter

org.apache.hadoop.util.bloom.BloomFilter

org.apache.hadoop.util.bloom.RetouchedBloomFilter

All Implemented Interfaces:

Writable, RemoveScheme

@InterfaceAudience.Public
 @InterfaceStability.Stable
public final class RetouchedBloomFilter
extends BloomFilter
implements RemoveScheme

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.

See Also:

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 Negatives

Field 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

Constructors

Constructor and Description
RetouchedBloomFilter() Default constructor - use with readFields
RetouchedBloomFilter(int vectorSize, int nbHash, int hashType) Constructor

Method Summary

Modifier and Type	Method and Description
void	add(org.apache.hadoop.util.bloom.Key key) Adds a key to this filter.
void	addFalsePositive(Collection<org.apache.hadoop.util.bloom.Key> coll) Adds a collection of false positive information to this retouched Bloom filter.
void	addFalsePositive(org.apache.hadoop.util.bloom.Key key) Adds a false positive information to this retouched Bloom filter.
void	addFalsePositive(org.apache.hadoop.util.bloom.Key[] keys) Adds an array of false positive information to this retouched Bloom filter.
void	addFalsePositive(List<org.apache.hadoop.util.bloom.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(org.apache.hadoop.util.bloom.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

RetouchedBloomFilter

public RetouchedBloomFilter()

Default constructor - use with readFields

RetouchedBloomFilter

public RetouchedBloomFilter(int vectorSize,
                            int nbHash,
                            int hashType)

Constructor

Parameters:

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

add

public void add(org.apache.hadoop.util.bloom.Key key)

Description copied from class: org.apache.hadoop.util.bloom.Filter

Adds a key to this filter.

Overrides:

add in class BloomFilter

Parameters:

key - The key to add.

addFalsePositive

public void addFalsePositive(org.apache.hadoop.util.bloom.Key key)

Adds a false positive information to this retouched Bloom filter.

Invariant: if the false positive is null, nothing happens.

Parameters:

key - The false positive key to add.

addFalsePositive

public void addFalsePositive(Collection<org.apache.hadoop.util.bloom.Key> coll)

Adds a collection of false positive information to this retouched Bloom filter.

Parameters:

coll - The collection of false positive.

addFalsePositive

public void addFalsePositive(List<org.apache.hadoop.util.bloom.Key> keys)

Adds a list of false positive information to this retouched Bloom filter.

Parameters:

keys - The list of false positive.

addFalsePositive

public void addFalsePositive(org.apache.hadoop.util.bloom.Key[] keys)

Adds an array of false positive information to this retouched Bloom filter.

Parameters:

keys - The array of false positive.

selectiveClearing

public void selectiveClearing(org.apache.hadoop.util.bloom.Key k,
                              short scheme)

Performs the selective clearing for a given key.

Parameters:

k - The false positive key to remove from this retouched Bloom filter.

scheme - The selective clearing scheme to apply.

write

public void write(DataOutput out)
           throws IOException

Description copied from interface: Writable

Serialize the fields of this object to out.

Specified by:

write in interface Writable

Overrides:

write in class BloomFilter

Parameters:

out - DataOuput to serialize this object into.

Throws:

IOException - any other problem for write.

readFields

public void readFields(DataInput in)
                throws IOException

Description copied from interface: Writable

Deserialize the fields of this object from in.

For efficiency, implementations should attempt to re-use storage in the existing object where possible.

Specified by:

readFields in interface Writable

Overrides:

readFields in class BloomFilter

Parameters:

in - DataInput to deseriablize this object from.

Throws:

IOException - any other problem for readFields.