Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## org.apache.hadoop.util.bloom
Class DynamicBloomFilter

    java.lang.Object
      org.apache.hadoop.util.bloom.Filter
          org.apache.hadoop.util.bloom.DynamicBloomFilter

All Implemented Interfaces:
  Writable

    public class DynamicBloomFilter

extends Filter

Implements a dynamic Bloom filter, as defined in the INFOCOM 2006 paper.

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.

See Also:
  `The general behavior of a filter`, `A Bloom filter`, Theory and Network Applications of Dynamic Bloom Filters

Field Summary

Fields inherited from class org.apache.hadoop.util.bloom.Filter
`hash, hashType, nbHash, vectorSize`

Constructor Summary
`DynamicBloomFilter()` Zero-args constructor for the serialization.
`DynamicBloomFilter(int vectorSize, int nbHash, int hashType, int nr)` Constructor.

Method Summary
`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.

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

### DynamicBloomFilter

    public DynamicBloomFilter()

  Zero-args constructor for the serialization.

### DynamicBloomFilter

    public DynamicBloomFilter(int vectorSize,
                              int nbHash,
                              int hashType,
                              int nr)

  Constructor.

  Builds an empty Dynamic Bloom filter.

  Parameters:
    `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.

Method Detail

### add

    public void add(Key key)

  Description copied from class: `Filter`
  Adds a key to this filter.

  Specified by:
    `add` in class `Filter`
  Parameters:
    `key` - The key to add.

### and

    public void and(Filter filter)

  Description copied from class: `Filter`
  Peforms a logical AND between this filter and a specified filter.

  Invariant: The result is assigned to this filter.

  Specified by:
    `and` in class `Filter`
  Parameters:
    `filter` - The filter to AND with.

### membershipTest

    public boolean membershipTest(Key key)

  Description copied from class: `Filter`
  Determines wether a specified key belongs to this filter.

  Specified by:
    `membershipTest` in class `Filter`
  Parameters:
    `key` - The key to test.
  Returns:
    boolean True if the specified key belongs to this filter. False otherwise.

### not

    public void not()

  Description copied from class: `Filter`
  Performs a logical NOT on this filter.

  The result is assigned to this filter.

  Specified by:
    `not` in class `Filter`

### or

    public void or(Filter filter)

  Description copied from class: `Filter`
  Peforms a logical OR between this filter and a specified filter.

  Invariant: The result is assigned to this filter.

  Specified by:
    `or` in class `Filter`
  Parameters:
    `filter` - The filter to OR with.

### xor

    public void xor(Filter filter)

  Description copied from class: `Filter`
  Peforms a logical XOR between this filter and a specified filter.

  Invariant: The result is assigned to this filter.

  Specified by:
    `xor` in class `Filter`
  Parameters:
    `filter` - The filter to XOR with.

### toString

    public String toString()

  Overrides:
    `toString` in class `Object`

### 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 `Filter`
  Parameters:
    `out` - `DataOuput` to serialize this object into.
  Throws:
    `IOException`

### 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 `Filter`
  Parameters:
    `in` - `DataInput` to deseriablize this object from.
  Throws:
    `IOException`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

Copyright © 2009 The Apache Software Foundation