orestes.bloomfilter

Class FilterBuilder

java.lang.Object

orestes.bloomfilter.FilterBuilder

All Implemented Interfaces:

java.io.Serializable, java.lang.Cloneable

public class FilterBuilder
extends java.lang.Object
implements java.lang.Cloneable, java.io.Serializable

Builder for Bloom Filters.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
FilterBuilder() Constructs a new builder for Bloom filters and counting Bloom filters.
FilterBuilder(int expectedElements, double falsePositiveProbability) Constructs a new Bloom Filter Builder by specifying the expected size of the filter and the tolerable false positive probability.
FilterBuilder(int size, int hashes) Constructs a new Bloom Filter Builder using the specified size in bits and the specified number of hash functions.

Method Summary

Modifier and Type	Method and Description
FilterBuilder	addReadSlave(java.lang.String host, int port) Adds a read slave to speed up reading access (e.g. contains or getEstimatedCount) to normal and counting Redis-backed Bloom filters.
<T> BloomFilter<T>	buildBloomFilter() Constructs a Bloom filter using the specified parameters and computing missing parameters if possible (e.g.
<T> CountingBloomFilter<T>	buildCountingBloomFilter() Constructs a Counting Bloom filter using the specified parameters and by computing missing parameters if possible (e.g.
FilterBuilder	clone()
FilterBuilder	complete() Checks if all necessary parameters were set and tries to infer optimal parameters (e.g. size and hashes from given expectedElements and falsePositiveProbability).
int	countingBits()
FilterBuilder	countingBits(int countingBits) Sets the number of bits used for counting in case of a counting Bloom filter.
static java.nio.charset.Charset	defaultCharset()
int	expectedElements()
FilterBuilder	expectedElements(int expectedElements) Sets the number of expected elements.
double	falsePositiveProbability()
FilterBuilder	falsePositiveProbability(double falsePositiveProbability) Sets the tolerable false positive probability.
java.util.Set<java.util.Map.Entry<java.lang.String,java.lang.Integer>>	getReadSlaves()
int	hashes()
FilterBuilder	hashes(int numberOfHashes) Set the number of hash functions to be used.
HashProvider.HashFunction	hashFunction()
FilterBuilder	hashFunction(HashProvider.HashFunction hf) Uses a given custom hash function.
FilterBuilder	hashFunction(HashProvider.HashMethod hashMethod) Sets the method used to generate hash values.
HashProvider.HashMethod	hashMethod()
boolean	isCompatibleTo(FilterBuilder other) Checks wether a configuration is compatible to another configuration based on the size of the Bloom filter and its hash functions.
java.lang.String	name()
FilterBuilder	name(java.lang.String name) Sets the name of the Bloom filter.
static int	optimalK(long n, long m) Calculates the optimal hashes (number of hash function) given expectedElements (expected number of elements in bloom filter) and size (size of bloom filter in bits).
static int	optimalM(long n, double p) Calculates the optimal size size of the bloom filter in bits given expectedElements (expected number of elements in bloom filter) and falsePositiveProbability (tolerable false positive rate).
static int	optimalN(long k, long m) Calculates the amount of elements a Bloom filter for which the given configuration of size and hashes is optimal.
static double	optimalP(long k, long m, double insertedElements) Calcluates the best-case (uniform hash function) false positive probability.
boolean	overwriteIfExists()
FilterBuilder	overwriteIfExists(boolean overwrite) Sets whether any existing Bloom filter with same name should be overwritten in Redis.
boolean	redisBacked()
FilterBuilder	redisBacked(boolean redisBacked) Instructs the FilterBuilder to build a Redis-Backed Bloom filters.
int	redisConnections()
FilterBuilder	redisConnections(int numConnections) Sets the number of connections to use for Redis.
java.lang.String	redisHost()
FilterBuilder	redisHost(java.lang.String host) Sets the host of the backing Redis instance.
int	redisPort()
FilterBuilder	redisPort(int port) Sets the port of the backing Redis instance.
int	size()
FilterBuilder	size(int size) Sets the size of the filter in bits.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

FilterBuilder

public FilterBuilder()

Constructs a new builder for Bloom filters and counting Bloom filters.

FilterBuilder

public FilterBuilder(int expectedElements,
                     double falsePositiveProbability)

Constructs a new Bloom Filter Builder by specifying the expected size of the filter and the tolerable false positive probability. The size of the BLoom filter in in bits and the optimal number of hash functions will be inferred from this.

Parameters:

expectedElements - expected elements in the filter

falsePositiveProbability - tolerable false positive probability

FilterBuilder

public FilterBuilder(int size,
                     int hashes)

Constructs a new Bloom Filter Builder using the specified size in bits and the specified number of hash functions.

Parameters:

size - bit size of the Bloom filter

hashes - number of hash functions to use

Method Detail

expectedElements

public FilterBuilder expectedElements(int expectedElements)

Sets the number of expected elements. In combination with the tolerable false positive probability, this is used to infer the optimal size and optimal number of hash functions of the filter.

Parameters:

expectedElements - number of expected elements.

Returns:

the modified FilterBuilder (fluent interface)

size

public FilterBuilder size(int size)

Sets the size of the filter in bits.

Parameters:

size - size of the filter in bits

Returns:

the modified FilterBuilder (fluent interface)

falsePositiveProbability

public FilterBuilder falsePositiveProbability(double falsePositiveProbability)

Sets the tolerable false positive probability. In combination with the number of expected elements, this is used to infer the optimal size and optimal number of hash functions of the filter.

Parameters:

falsePositiveProbability - the tolerable false

Returns:

the modified FilterBuilder (fluent interface)

hashes

public FilterBuilder hashes(int numberOfHashes)

Set the number of hash functions to be used.

Parameters:

numberOfHashes - number of hash functions used by the filter.

Returns:

the modified FilterBuilder (fluent interface)

countingBits

public FilterBuilder countingBits(int countingBits)

Sets the number of bits used for counting in case of a counting Bloom filter. For non-counting Bloom filters this setting has no effect.

Default: 16

Parameters:

countingBits -

Returns:

the modified FilterBuilder (fluent interface)

name

public FilterBuilder name(java.lang.String name)

Sets the name of the Bloom filter. If a redis-backed Bloom filter with the provided name exists and it is compatible to this FilterBuilder configuration, it will be loaded and used. This behaviour can be changed by overwriteIfExists(boolean).

Default: ""

Parameters:

name -

Returns:

the modified FilterBuilder (fluent interface)

redisBacked

public FilterBuilder redisBacked(boolean redisBacked)

Instructs the FilterBuilder to build a Redis-Backed Bloom filters.

Default: false

Parameters:

redisBacked - a boolean indicating whether redis should be used

Returns:

the modified FilterBuilder (fluent interface)

redisHost

public FilterBuilder redisHost(java.lang.String host)

Sets the host of the backing Redis instance.

Default: localhost

Parameters:

host - the Redis host

Returns:

the modified FilterBuilder (fluent interface)

redisPort

public FilterBuilder redisPort(int port)

Sets the port of the backing Redis instance.

Default: 6379

Parameters:

port - the Redis port

Returns:

the modified FilterBuilder (fluent interface)

redisConnections

public FilterBuilder redisConnections(int numConnections)

Sets the number of connections to use for Redis.

Default: 10

Parameters:

numConnections - the number of connections to use for Redis

Returns:

the modified FilterBuilder (fluent interface)

overwriteIfExists

public FilterBuilder overwriteIfExists(boolean overwrite)

Sets whether any existing Bloom filter with same name should be overwritten in Redis.

Default: false

Parameters:

overwrite - boolean indicating whether to overwrite any existing filter with the same name

Returns:

the modified FilterBuilder (fluent interface)

addReadSlave

public FilterBuilder addReadSlave(java.lang.String host,
                                  int port)

Adds a read slave to speed up reading access (e.g. contains or getEstimatedCount) to normal and counting Redis-backed Bloom filters. The read slave has to be a slave of the main Redis instance (this can be done in the redis-cli using the SLAVEOF command). This setting might cause stale reads since Redis replication is asynchronous. However anecdotally, in our experiments, we were unable to read any stale data - the replication lag between both Redis instances was small than one round-trip time to Redis.

Parameters:

host - host of the Redis read slave

port - port of the Redis read slave

Returns:

the modified FilterBuilder (fluent interface)

hashFunction

public FilterBuilder hashFunction(HashProvider.HashMethod hashMethod)

Sets the method used to generate hash values. Possible hash methods are documented in the corresponding enum HashProvider.HashMethod.

Default: MD5

For the generation of hash values the String representation of objects is used.

Parameters:

hashMethod - the method used to generate hash values

Returns:

the modified FilterBuilder (fluent interface)

hashFunction

public FilterBuilder hashFunction(HashProvider.HashFunction hf)

Uses a given custom hash function.

Parameters:

hf - the custom hash function

Returns:

the modified FilterBuilder (fluent interface)

buildBloomFilter

public <T> BloomFilter<T> buildBloomFilter()

Constructs a Bloom filter using the specified parameters and computing missing parameters if possible (e.g. the optimal Bloom filter bit size).

Type Parameters:

T - the type of element contained in the Bloom filter.

Returns:

the constructed Bloom filter

buildCountingBloomFilter

public <T> CountingBloomFilter<T> buildCountingBloomFilter()

Constructs a Counting Bloom filter using the specified parameters and by computing missing parameters if possible (e.g. the optimal Bloom filter bit size).

Type Parameters:

T - the type of element contained in the Counting Bloom filter.

Returns:

the constructed Counting Bloom filter

complete

public FilterBuilder complete()

Checks if all necessary parameters were set and tries to infer optimal parameters (e.g. size and hashes from given expectedElements and falsePositiveProbability). This is done automatically.

clone

public FilterBuilder clone()

Overrides:

clone in class java.lang.Object

redisBacked

public boolean redisBacked()

Returns:

true if the Bloom Filter will be Redis-backed

expectedElements

public int expectedElements()

Returns:

the number of expected elements for the Bloom filter

size

public int size()

Returns:

the size of the Bloom filter in bits

hashes

public int hashes()

Returns:

the number of hashes used by the Bloom filter

countingBits

public int countingBits()

Returns:

The number of bits used for counting in case of a counting Bloom filter

falsePositiveProbability

public double falsePositiveProbability()

Returns:

the tolerable false positive probability of the Bloom filter

name

public java.lang.String name()

Returns:

the name of the Bloom filter

redisHost

public java.lang.String redisHost()

Returns:

the host name of the Redis server backing the Bloom filter

redisPort

public int redisPort()

Returns:

the port used by the Redis server backing the Bloom filter

redisConnections

public int redisConnections()

Returns:

the number of connections used by the Redis Server backing the Bloom filter

hashMethod

public HashProvider.HashMethod hashMethod()

Returns:

The hash method to be used by the Bloom filter

hashFunction

public HashProvider.HashFunction hashFunction()

Returns:

the actual hash function to be used by the Bloom filter

defaultCharset

public static java.nio.charset.Charset defaultCharset()

Returns:

Return the default Charset used for conversion of String values into byte arrays used for hashing

overwriteIfExists

public boolean overwriteIfExists()

Returns:

true if the Bloom filter that is to be built should overwrite any existing Bloom filter with the same name

getReadSlaves

public java.util.Set<java.util.Map.Entry<java.lang.String,java.lang.Integer>> getReadSlaves()

Returns:

return the list of all read slaves to be used by the Redis-backed Bloom filter

isCompatibleTo

public boolean isCompatibleTo(FilterBuilder other)

Checks wether a configuration is compatible to another configuration based on the size of the Bloom filter and its hash functions.

Parameters:

other - the other configuration

Returns:

true if the configurations are compatible

optimalM

public static int optimalM(long n,
                           double p)

Calculates the optimal size size of the bloom filter in bits given expectedElements (expected number of elements in bloom filter) and falsePositiveProbability (tolerable false positive rate).

Parameters:

n - Expected number of elements inserted in the bloom filter

p - Tolerable false positive rate

Returns:

the optimal size size of the bloom filter in bits

optimalK

public static int optimalK(long n,
                           long m)

Calculates the optimal hashes (number of hash function) given expectedElements (expected number of elements in bloom filter) and size (size of bloom filter in bits).

Parameters:

n - Expected number of elements inserted in the bloom filter

m - The size of the bloom filter in bits.

Returns:

the optimal amount of hash functions hashes

optimalN

public static int optimalN(long k,
                           long m)

Calculates the amount of elements a Bloom filter for which the given configuration of size and hashes is optimal.

Parameters:

k - number of hashes

m - The size of the bloom filter in bits.

Returns:

amount of elements a Bloom filter for which the given configuration of size and hashes is optimal.

optimalP

public static double optimalP(long k,
                              long m,
                              double insertedElements)

Calcluates the best-case (uniform hash function) false positive probability.

Parameters:

k - number of hashes

m - The size of the bloom filter in bits.

insertedElements - number of elements inserted in the filter

Returns: