org.edg.data.util
Class CountingBloomFilter

java.lang.Object
  |
  +--org.edg.data.util.BloomFilter
        |
        +--org.edg.data.util.CountingBloomFilter
All Implemented Interfaces:
java.io.Serializable

public class CountingBloomFilter
extends BloomFilter

A Representation of a Bloom Filter which stores counts for each bit. See The Math of Bloom Filters for how to tune the Filter. Note you must specify the size of the filter a priori (i.e. set m), but it can tell you when it has too many entries, and will start to degrade (i.e. more than n entries. We store the counts as a single nybble, i.e. 4 bits. We don't deal with overflow, so if the same bit is added more than 15 times, and then removed 15 times, the bit will be set to 0. The above reference shows the probability of this overflow happening is bounded by 1.37e-15 x m. We use MD5 to compute the hash functions, which are fixed to 4. We deal with bloom filters with up to 2^^31 bits in them.

Version:
$ Id:$
Author:
James Casey
See Also:
Serialized Form

Field Summary
 
Fields inherited from class org.edg.data.util.BloomFilter
m_bits
 
Constructor Summary
CountingBloomFilter(byte[] bits, int entries, int numBits, int optimalNumKeys)
          create a read-only Bloomfilter from a pre-created bit array.
CountingBloomFilter(int bitsPerEntry, int optimalNumKeys)
          create a new bloom filter
 
Method Summary
protected  void clearBit(int bit)
           
protected  boolean isSet(int bit)
           
protected  void setBit(int bit)
           
 
Methods inherited from class org.edg.data.util.BloomFilter
add, contains, delete, equals, getNumberOfHashes, getNumBits, getNumEntries, getOptimalNumKeys, hashCode, isFull, toString, writeBits
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Constructor Detail

CountingBloomFilter

public CountingBloomFilter(int bitsPerEntry,
                           int optimalNumKeys)
create a new bloom filter

Parameters:
bitsPerEntry - The number of bits per entry in the filter we require (also known as m/n)
optimalNumKeys - The number of keys for which this filter optimally support (also known as n)

CountingBloomFilter

public CountingBloomFilter(byte[] bits,
                           int entries,
                           int numBits,
                           int optimalNumKeys)
create a read-only Bloomfilter from a pre-created bit array.

Parameters:
bits - the bit array.
entries - current number of entries in filter
numBits - the number of bits in this filter
optimalNumKeys - The number of keys for which this filter optimally support (also known as n)
Method Detail

setBit

protected void setBit(int bit)
Specified by:
setBit in class BloomFilter

clearBit

protected void clearBit(int bit)
Specified by:
clearBit in class BloomFilter

isSet

protected boolean isSet(int bit)
Specified by:
isSet in class BloomFilter