orestes.bloomfilter

Interface CountingBloomFilter<T>

All Superinterfaces:

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

All Known Implementing Classes:

CountingBloomFilterMemory, CountingBloomFilterRedis

public interface CountingBloomFilter<T>
extends BloomFilter<T>

Represents a Counting Bloom Filter, which in contrast to a normal Bloom filter also allow removal.

Method Summary

Modifier and Type	Method and Description
default boolean	add(byte[] element) Adds the passed value to the filter.
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).
default long	addAndEstimateCount(T 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).
CountingBloomFilter<T>	clone() Constructs a deep copy of the Bloom filter
default int	getCountingBits()
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).
default boolean	remove(byte[] element) Removes the object from the counting bloom filter.
default boolean	remove(T element) Removes the object from the counting bloom filter.
default java.util.List<java.lang.Boolean>	removeAll(java.util.Collection<T> elements) Removes the objects from the counting bloom filter.
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).
default long	removeAndEstimateCount(T 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).

Methods inherited from interface orestes.bloomfilter.BloomFilter

add, addAll, asString, clear, compatible, config, contains, contains, contains, containsAll, getBitSet, getBitsPerElement, getBitZeroProbability, getEstimatedFalsePositiveProbability, getEstimatedPopulation, getExpectedElements, getFalsePositiveProbability, getFalsePositiveProbability, getHashes, getSize, hash, hash, intersect, isEmpty, population, remove, toBytes, union

Method Detail

getCountingBits

default int getCountingBits()

Returns:

the number of bits used for counting

add

default boolean add(byte[] element)

Description copied from interface: BloomFilter

Adds the passed value to the filter.

Specified by:

add in interface BloomFilter<T>

Parameters:

element - value to add

Returns:

true if the value did not previously exist in the filter. Note, that a false positive may occur, thus the value may not have already been in the filter, but it hashed to a set of bits already in the filter.

remove

default boolean remove(byte[] element)

Removes the object from the counting bloom filter.

Parameters:

element - object to be deleted

Returns:

true if the element is not present after removal

remove

default boolean remove(T element)

Removes the object from the counting bloom filter.

Parameters:

element - object to be deleted

Returns:

true if the element is not present after removal

removeAll

default java.util.List<java.lang.Boolean> removeAll(java.util.Collection<T> elements)

Removes the objects from the counting bloom filter.

Parameters:

elements - objects to be deleted

Returns:

a list of booleans indicating for each element, whether it was removed

getEstimatedCount

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

Parameters:

element - element to query

Returns:

estimated count of the element

addAndEstimateCount

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

Parameters:

element - element to add

Returns:

estimated frequency of the element after insertion

addAndEstimateCount

default long addAndEstimateCount(T 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).

Parameters:

element - element to add

Returns:

estimated frequency of the element after insertion

removeAndEstimateCount

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

Parameters:

element - element to remove

Returns:

estimated frequency of the element after deletion

removeAndEstimateCount

default long removeAndEstimateCount(T 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).

Parameters:

element - element to remove

Returns:

estimated frequency of the element after deletion

clone

CountingBloomFilter<T> clone()

Description copied from interface: BloomFilter

Constructs a deep copy of the Bloom filter

Specified by:

clone in interface BloomFilter<T>

Returns:

copy of the filter.