org.forgerock.bloomfilter

Class BloomFilters.BloomFilterBuilder<T>

java.lang.Object

org.forgerock.bloomfilter.BloomFilters.BloomFilterBuilder<T>

Direct Known Subclasses:

BloomFilters.ScalableBloomFilterBuilder

Enclosing class:

BloomFilters

public static class BloomFilters.BloomFilterBuilder<T>
extends Object

Builder for constructing and configuring Bloom Filter implementations.

Method Summary

Modifier and Type	Method and Description
BloomFilter<T>	build() Builds the bloom filter with the configured options.
BloomFilters.RollingBloomFilterBuilder<T>	rolling() Forces the bloom filter to be a Rolling Bloom Filter, which is a variant on Scalable Bloom Filters where elements in the bloom filter can expire allowing space to be reclaimed.
BloomFilters.ScalableBloomFilterBuilder<T>	scalable() Forces the bloom filter to be a Scalable Bloom Filter which can expand to arbitrary capacity.
BloomFilters.ScalableBloomFilterBuilder<T>	withCapacityGrowthFactor(double growthFactor) The factor by which to increase the capacity of the bloom filter when it exceeds the initial capacity.
BloomFilters.BloomFilterBuilder<T>	withConcurrencyStrategy(ConcurrencyStrategy strategy) Sets the strategy to use for managing thread-safety in the bloom filter.
BloomFilters.RollingBloomFilterBuilder<T>	withExpiryStrategy(ExpiryStrategy<T> expiryStrategy) Strategy for determining when elements of a rolling bloom filter have expired.
BloomFilters.BloomFilterBuilder<T>	withFalsePositiveProbability(double fpp) Specifies the overall probability of false positives that this bloom filter should achieve.
BloomFilters.ScalableBloomFilterBuilder<T>	withFalsePositiveProbabilityScaleFactor(double scaleFactor) The factor by which to reduce the probability of false positives when expanding a scalable/rolling bloom filter.
BloomFilters.BloomFilterBuilder<T>	withInitialCapacity(int capacity) Specifies the initial capacity of the bloom filter.
BloomFilters.ScalableBloomFilterBuilder<T>	withMaximumNumberOfBuckets(int maximumNumberOfBuckets) Sets the maximum number of buckets to create before throwing an exception indicating the maximum capacity has been reached.
BloomFilters.BloomFilterBuilder<T>	withWriteBatchSize(int batchSize) Enables batching of writes to the bloom filter.

Methods inherited from class java.lang.Object

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

Method Detail

withInitialCapacity

public BloomFilters.BloomFilterBuilder<T> withInitialCapacity(int capacity)

Specifies the initial capacity of the bloom filter. This is the expected number of elements that can be inserted into the bloom filter before it becomes saturated (exceeds the configured false positive probability).

Parameters:

capacity - the initial capacity of the bloom filter.

withFalsePositiveProbability

public BloomFilters.BloomFilterBuilder<T> withFalsePositiveProbability(double fpp)

Specifies the overall probability of false positives that this bloom filter should achieve. The bloom filter will be sized to achieve this probability for the specified capacity.

Parameters:

fpp - the probability of false positives to achieve.

withCapacityGrowthFactor

public BloomFilters.ScalableBloomFilterBuilder<T> withCapacityGrowthFactor(double growthFactor)

The factor by which to increase the capacity of the bloom filter when it exceeds the initial capacity. A factor of 1 will increase the capacity linearly, which may result in an explosion in the number of buckets if the expected capacity of the filter has been underestimated. The default factor is 2, which ensures that the bloom filter quickly grows to be "large enough" without creating a large number of buckets (i.e., the number of buckets created will be logarithmic in the total number of insertions).

Parameters:

growthFactor - the factor by which to increase bloom filter capacity when expanding.

withFalsePositiveProbabilityScaleFactor

public BloomFilters.ScalableBloomFilterBuilder<T> withFalsePositiveProbabilityScaleFactor(double scaleFactor)

The factor by which to reduce the probability of false positives when expanding a scalable/rolling bloom filter. As the overall false positive probability (FPP) is the sum of the probabilities of each component bloom filter in the chain, the FPP of each subsequent bucket is reduced by this factor so that the sum never exceeds the overall FPP. A factor close to 1 will reduce the FPP slowly, limiting the additional memory used on each expansion, but with the trade-off of using more memory initially. A lower number will use less memory initially but then decrease the FPP more rapidly, resulting in increased memory usage. The default setting (0.8) is tuned for scalable bloom filters that grow unbounded over time. It is recommended to reduce the factor in rolling bloom filters where the chain is expected not to grow beyond a few buckets in size.

Parameters:

scaleFactor - the factor by which to decrease the false positive probability when expanding.

withMaximumNumberOfBuckets

public BloomFilters.ScalableBloomFilterBuilder<T> withMaximumNumberOfBuckets(int maximumNumberOfBuckets)

Sets the maximum number of buckets to create before throwing an exception indicating the maximum capacity has been reached. Defaults to unlimited.

Parameters:

maximumNumberOfBuckets - the maximum number of buckets to create.

withExpiryStrategy

public BloomFilters.RollingBloomFilterBuilder<T> withExpiryStrategy(ExpiryStrategy<T> expiryStrategy)

Strategy for determining when elements of a rolling bloom filter have expired. Used to determine when all elements in a bucket have expired and so can be released.

Parameters:

expiryStrategy - strategy for determining element expiry time.

withConcurrencyStrategy

public BloomFilters.BloomFilterBuilder<T> withConcurrencyStrategy(ConcurrencyStrategy strategy)

Sets the strategy to use for managing thread-safety in the bloom filter.

Parameters:

strategy - the concurrency strategy to use.

withWriteBatchSize

public BloomFilters.BloomFilterBuilder<T> withWriteBatchSize(int batchSize)

Enables batching of writes to the bloom filter. This can significantly increase the performance of write-heavy workloads at the expense of using additional memory and reducing the accuracy of the result of the add/addAll methods. It is recommended to enable this setting when using the ConcurrencyStrategy.COPY_ON_WRITE strategy.

Parameters:

batchSize - the number of elements to buffer before writing to the bloom filter.

scalable

public BloomFilters.ScalableBloomFilterBuilder<T> scalable()

Forces the bloom filter to be a Scalable Bloom Filter which can expand to arbitrary capacity.

See Also:

Scalable Bloom Filters by Almeida et al., Information Processing Letters, 101(6), p.255–261, 2007.

rolling

public BloomFilters.RollingBloomFilterBuilder<T> rolling()

Forces the bloom filter to be a Rolling Bloom Filter, which is a variant on Scalable Bloom Filters where elements in the bloom filter can expire allowing space to be reclaimed.

build

public BloomFilter<T> build()

Builds the bloom filter with the configured options.

Returns:

a new bloom filter configured appropriately.