Package 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
@Public @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:

  • 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
    Description
    RetouchedBloomFilter()
    Default constructor - use with readFields
    RetouchedBloomFilter(int vectorSize, int nbHash, int hashType)
    Constructor

  • Method Summary

    Modifier and Type
    Method
    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(List<org.apache.hadoop.util.bloom.Key> keys)
    Adds a list 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
    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 Details

    • 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 Details

    • 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.