org.onelab.filter
Class CountingBloomFilter

java.lang.Object
  org.onelab.filter.Filter
      org.onelab.filter.CountingBloomFilter

All Implemented Interfaces:

Comparable, Writable, WritableComparable

public final class CountingBloomFilter
extends Filter

Implements a counting Bloom filter, as defined by Fan et al. in a ToN 2000 paper.

A counting Bloom filter is an improvement to standard a Bloom filter as it allows dynamic additions and deletions of set membership information. This is achieved through the use of a counting vector instead of a bit vector. contract European Commission One-Lab Project 034819.

Version:

1.0 - 5 Feb. 07

See Also:

The general behavior of a filter, Summary cache: a scalable wide-area web cache sharing protocol

Field Summary

Fields inherited from class org.onelab.filter.Filter

hash

Constructor Summary

CountingBloomFilter()
Default constructor - use with readFields

CountingBloomFilter(int vectorSize, int nbHash)
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.
Object	clone()
int	compareTo(Object o)
void	delete(Key key) Removes a specified key from this counting Bloom filter.
boolean	equals(Object o)
int	hashCode()
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. For efficiency, implementations should attempt to re-use storage in the existing object where possible.
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.onelab.filter.Filter

add, add, add

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

CountingBloomFilter

public CountingBloomFilter()

Default constructor - use with readFields

CountingBloomFilter

public CountingBloomFilter(int vectorSize,
                           int nbHash)

Constructor

Parameters:

vectorSize - The vector size of this filter.

nbHash - The number of hash function to consider.

Method Detail

add

public void add(Key key)

Adds a key to this filter.

Specified by:

add in class Filter

Parameters:

key - The key to add.

delete

public void delete(Key key)

Removes a specified key from this counting Bloom filter.

Invariant: nothing happens if the specified key does not belong to this counter Bloom filter.

Parameters:

key - The key to remove.

and

public void and(Filter 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)

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()

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)

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)

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

clone

public Object clone()

Overrides:

clone in class Object

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Filter

write

public void write(DataOutput out)
           throws IOException

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

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

compareTo

public int compareTo(Object o)

Specified by:

compareTo in interface Comparable

Overrides:

compareTo in class Filter