orestes.bloomfilter.memory

Class CountingBloomFilterMemory<T>

java.lang.Object

orestes.bloomfilter.memory.CountingBloomFilterMemory<T>

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable, BloomFilter<T>, CountingBloomFilter<T>

public class CountingBloomFilterMemory<T>
extends java.lang.Object
implements CountingBloomFilter<T>

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
CountingBloomFilterMemory(FilterBuilder config)

Method Summary

Modifier and Type	Method and Description
long	addAndEstimateCount(byte[] element) Adds an element and returns its estimated frequency after the insertion (i.e. the number of times the element was added to the filter).
void	clear() Removes all elements from the filter (i.e. resets all bits to zero).
CountingBloomFilterMemory<T>	clone() Constructs a deep copy of the Bloom filter
FilterBuilder	config() Returns the configuration/builder of the Bloom filter.
boolean	contains(byte[] element) Tests whether an element is present in the filter (subject to the specified false positive rate).
protected long	count(int index)
protected long	decrement(int index) Decrements the internal counter upon deletion and unsets the Bloom filter bit if necessary.
boolean	equals(java.lang.Object o)
java.util.BitSet	getBitSet() Return the underyling bit vector of the Bloom filter.
long	getEstimatedCount(T element) Return the estimated count for an element using the Mininum Selection algorithm (i.e. by choosing the minimum counter for the given element).
protected long	increment(int index) Increment the internal counter upon insertion of new elements.
boolean	intersect(BloomFilter<T> other) Performs the intersection operation on two compatible bloom filters.
boolean	isEmpty() Returns true if the Bloom filter does not contain any elements
long	removeAndEstimateCount(byte[] element) Removes an element and returns its estimated frequency after the insertion (i.e. the number of times the element was added to the filter).
void	setOverflowHandler(java.lang.Runnable callback)
java.lang.String	toString()
boolean	union(BloomFilter<T> other) Performs the union operation on two compatible bloom filters.

Methods inherited from class java.lang.Object

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

Methods inherited from interface orestes.bloomfilter.CountingBloomFilter

add, addAndEstimateCount, getCountingBits, remove, remove, removeAll, removeAndEstimateCount

Methods inherited from interface orestes.bloomfilter.BloomFilter

add, addAll, asString, compatible, contains, contains, containsAll, getBitsPerElement, getBitZeroProbability, getEstimatedFalsePositiveProbability, getEstimatedPopulation, getExpectedElements, getFalsePositiveProbability, getFalsePositiveProbability, getHashes, getSize, hash, hash, population, remove, toBytes

Constructor Detail

CountingBloomFilterMemory

public CountingBloomFilterMemory(FilterBuilder config)

Method Detail

contains

public boolean contains(byte[] element)

Description copied from interface: BloomFilter

Tests whether an element is present in the filter (subject to the specified false positive rate).

Specified by:

contains in interface BloomFilter<T>

Returns:

true if the element is contained

addAndEstimateCount

public long addAndEstimateCount(byte[] element)

Description copied from interface: CountingBloomFilter

Adds an element and returns its estimated frequency after the insertion (i.e. the number of times the element was added to the filter).

Specified by:

addAndEstimateCount in interface CountingBloomFilter<T>

Parameters:

element - element to add

Returns:

estimated frequency of the element after insertion

removeAndEstimateCount

public long removeAndEstimateCount(byte[] element)

Description copied from interface: CountingBloomFilter

Removes an element and returns its estimated frequency after the insertion (i.e. the number of times the element was added to the filter).

Specified by:

removeAndEstimateCount in interface CountingBloomFilter<T>

Parameters:

element - element to remove

Returns:

estimated frequency of the element after deletion

increment

protected long increment(int index)

Increment the internal counter upon insertion of new elements.

Parameters:

index - position at which to increase

count

protected long count(int index)

decrement

protected long decrement(int index)

Decrements the internal counter upon deletion and unsets the Bloom filter bit if necessary.

Parameters:

index - position at which to decrease

getEstimatedCount

public long getEstimatedCount(T element)

Description copied from interface: CountingBloomFilter

Return the estimated count for an element using the Mininum Selection algorithm (i.e. by choosing the minimum counter for the given element). This estimation is biased, as it doest not consider how full the filter is, but performs best in practice. The underlying theoretical foundation are spectral Bloom filters, see: http://theory.stanford.edu/~matias/papers/sbf_thesis.pdf

Specified by:

getEstimatedCount in interface CountingBloomFilter<T>

Parameters:

element - element to query

Returns:

estimated count of the element

union

public boolean union(BloomFilter<T> other)

Description copied from interface: BloomFilter

Performs the union operation on two compatible bloom filters. This is achieved through a bitwise OR operation on their bit vectors. This operations is lossless, i.e. no elements are lost and the bloom filter is the same that would have resulted if all elements wer directly inserted in just one bloom filter.

Specified by:

union in interface BloomFilter<T>

Parameters:

other - the other bloom filter

Returns:

true if this bloom filter could successfully be updated through the union with the provided bloom filter

intersect

public boolean intersect(BloomFilter<T> other)

Description copied from interface: BloomFilter

Performs the intersection operation on two compatible bloom filters. This is achieved through a bitwise AND operation on their bit vectors. The operations doesn't introduce any false negatives but it does raise the false positive probability. The the false positive probability in the resulting Bloom filter is at most the false-positive probability in one of the constituent bloom filters

Specified by:

intersect in interface BloomFilter<T>

Parameters:

other - the other bloom filter

Returns:

true if this bloom filter could successfully be updated through the intersection with the provided bloom filter

isEmpty

public boolean isEmpty()

Description copied from interface: BloomFilter

Returns true if the Bloom filter does not contain any elements

Specified by:

isEmpty in interface BloomFilter<T>

Returns:

true if the Bloom filter does not contain any elements

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

clone

public CountingBloomFilterMemory<T> clone()

Description copied from interface: BloomFilter

Constructs a deep copy of the Bloom filter

Specified by:

clone in interface BloomFilter<T>

Specified by:

clone in interface CountingBloomFilter<T>

Overrides:

clone in class java.lang.Object

Returns:

copy of the filter.

clear

public void clear()

Description copied from interface: BloomFilter

Removes all elements from the filter (i.e. resets all bits to zero).

Specified by:

clear in interface BloomFilter<T>

getBitSet

public java.util.BitSet getBitSet()

Description copied from interface: BloomFilter

Return the underyling bit vector of the Bloom filter.

Specified by:

getBitSet in interface BloomFilter<T>

Returns:

the underyling bit vector of the Bloom filter.

config

public FilterBuilder config()

Description copied from interface: BloomFilter

Returns the configuration/builder of the Bloom filter.

Specified by:

config in interface BloomFilter<T>

Returns:

the configuration/builder of the Bloom filter.

equals

public boolean equals(java.lang.Object o)

Overrides:

equals in class java.lang.Object

setOverflowHandler

public void setOverflowHandler(java.lang.Runnable callback)