Package org.apache.commons.collections4.bloomfilter

Class LayeredBloomFilter<T extends BloomFilter<T>>

  • Type Parameters:
    T - The type of Bloom Filter that is used for the layers.
    All Implemented Interfaces:
    BitMapExtractor, BloomFilter<LayeredBloomFilter<T>>, BloomFilterExtractor, IndexExtractor
    public class LayeredBloomFilter<T extends BloomFilter<T>>
extends java.lang.Object
implements BloomFilter<LayeredBloomFilter<T>>, BloomFilterExtractor
    Layered Bloom filters are described in Zhiwang, Cen; Jungang, Xu; Jian, Sun (2010), "A multi-layer Bloom filter for duplicated URL detection", Proc. 3rd International Conference on Advanced Computer Theory and Engineering (ICACTE 2010), vol. 1, pp. V1-586-V1-591, doi:10.1109/ICACTE.2010.5578947, ISBN 978-1-4244-6539-2, S2CID 3108985

    In short, Layered Bloom filter contains several bloom filters arranged in layers.

    • When membership in the filter is checked each layer in turn is checked and if a match is found true is returned.
    • When merging each bloom filter is merged into the newest filter in the list of layers.
    • When questions of cardinality are asked the cardinality of the union of the enclosed Bloom filters is used.

    The net result is that the layered Bloom filter can be populated with more items than the Shape would indicate and yet still return a false positive rate in line with the Shape and not the over population.

    This implementation uses a LayerManager to handle the manipulation of the layers.

    • Level 0 is the oldest layer and the highest level is the newest.
    • There is always at least one enclosed filter.
    • The newest filter is the target into which merges are performed.
    • Whenever the target is retrieved, or a merge operation is performed the code checks if any older layers should be removed, and if so removes them. It also checks it a new layer should be added, and if so adds it and sets the target before the operation.
    Since:
    4.5.0-M2

    • Field Summary

      • Fields inherited from interface org.apache.commons.collections4.bloomfilter.BloomFilter

        SPARSE

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int cardinality()
      Gets the cardinality (number of enabled bits) of this Bloom filter.
      int characteristics()
      Gets the characteristics of the filter.
      void cleanup()
      Forces the execution of the cleanup Consumer that was provided when the associated LayerManager was built.
      void clear()
      Clears the filter to by resetting it to its initial, unpopulated state.
      boolean contains​(BitMapExtractor bitMapExtractor)
      Returns true if this filter contains the bits specified in the bit maps produced by the bitMapExtractor.
      boolean contains​(BloomFilter other)
      Returns true if this any layer contained by this filter contains the specified filter.
      boolean contains​(BloomFilterExtractor bloomFilterExtractor)
      Returns true if each filter within the bloomFilterExtractor exits within this filter.
      boolean contains​(Hasher hasher)
      Returns true if this filter contains the bits specified in the hasher.
      boolean contains​(IndexExtractor indexExtractor)
      Returns true if this filter contains the indices specified IndexExtractor.
      LayeredBloomFilter<T> copy()
      Creates a new instance of this LayeredBloomFilter with the same properties as the current one.
      int estimateN()
      Estimates the number of items in the Bloom filter.
      int estimateUnion​(BloomFilter other)
      Estimates the number of items in the union of this Bloom filter with the other bloom filter.
      int[] find​(BitMapExtractor bitMapExtractor)
      Finds the layers in which the BitMapExtractor is found.
      int[] find​(BloomFilter bf)
      Finds the layers in which the Bloom filter is found.
      int[] find​(Hasher hasher)
      Finds the layers in which the Hasher is found.
      int[] find​(IndexExtractor indexExtractor)
      Finds the layers in which the IndexExtractor is found.
      SimpleBloomFilter flatten()
      Create a standard (non-layered) Bloom filter by merging all of the layers.
      T get​(int depth)
      Gets the Bloom filter at the specified depth
      int getDepth()
      Gets the depth of the deepest layer.
      Shape getShape()
      Gets the shape that was used when the filter was built.
      boolean isEmpty()
      Determines if all the bits are off.
      boolean merge​(BitMapExtractor bitMapExtractor)
      Merges the specified hasher into this Bloom filter.
      boolean merge​(BloomFilter bf)
      Merges the specified Bloom filter into this Bloom filter.
      boolean merge​(IndexExtractor indexExtractor)
      Merges the specified IndexExtractor into this Bloom filter.
      void next()
      Forces and advance to the next layer.
      boolean processBitMaps​(java.util.function.LongPredicate predicate)
      Each bit map is passed to the predicate in order.
      boolean processBloomFilters​(java.util.function.Predicate<BloomFilter> bloomFilterPredicate)
      Processes the Bloom filters in depth order with the most recent filters first.
      boolean processIndices​(java.util.function.IntPredicate predicate)
      Each index is passed to the predicate.

      • Methods inherited from class java.lang.Object

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

    • Constructor Detail

      • LayeredBloomFilter

        public LayeredBloomFilter​(Shape shape,
                          LayerManager<T> layerManager)
        Constructs a new instance.
        Parameters:
        shape - the Shape of the enclosed Bloom filters
        layerManager - the LayerManager to manage the layers.

    • Method Detail

      • cardinality

        public int cardinality()
        Description copied from interface: BloomFilter
        Gets the cardinality (number of enabled bits) of this Bloom filter.

        This is also known as the Hamming value or Hamming number.

        Specified by:
        cardinality in interface BloomFilter<T extends BloomFilter<T>>
        Returns:
        the cardinality of this filter

      • characteristics

        public int characteristics()
        Description copied from interface: BloomFilter
        Gets the characteristics of the filter.

        Characteristics are defined as bits within the characteristics integer.

        Specified by:
        characteristics in interface BloomFilter<T extends BloomFilter<T>>
        Returns:
        the characteristics for this bloom filter.

      • clear

        public final void clear()
        Description copied from interface: BloomFilter
        Clears the filter to by resetting it to its initial, unpopulated state.
        Specified by:
        clear in interface BloomFilter<T extends BloomFilter<T>>

      • contains

        public boolean contains​(BitMapExtractor bitMapExtractor)
        Description copied from interface: BloomFilter
        Returns true if this filter contains the bits specified in the bit maps produced by the bitMapExtractor.
        Specified by:
        contains in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        bitMapExtractor - the BitMapExtractor to provide the bit maps.
        Returns:
        true if this filter is enabled for all bits specified by the bit maps

      • contains

        public boolean contains​(BloomFilter other)
        Returns true if this any layer contained by this filter contains the specified filter.

        If the other is a BloomFilterExtractor each filter within the other is checked to see if it exits within this filter.

        Specified by:
        contains in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        other - the other Bloom filter
        Returns:
        true if this filter contains the other filter.

      • contains

        public boolean contains​(BloomFilterExtractor bloomFilterExtractor)
        Returns true if each filter within the bloomFilterExtractor exits within this filter.
        Parameters:
        bloomFilterExtractor - the BloomFilterExtractor that provides the filters to check for.
        Returns:
        true if this filter contains all of the filters contained in the bloomFilterExtractor.

      • contains

        public boolean contains​(Hasher hasher)
        Description copied from interface: BloomFilter
        Returns true if this filter contains the bits specified in the hasher.

        Specifically this returns true if this filter is enabled for all bit indexes identified by the hasher. Using the bit map representations this is effectively (this AND hasher) == hasher.

        Specified by:
        contains in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        hasher - the hasher to provide the indexes
        Returns:
        true if this filter is enabled for all bits specified by the hasher

      • contains

        public boolean contains​(IndexExtractor indexExtractor)
        Description copied from interface: BloomFilter
        Returns true if this filter contains the indices specified IndexExtractor.

        Specifically this returns true if this filter is enabled for all bit indexes identified by the IndexExtractor.

        Specified by:
        contains in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        indexExtractor - the IndexExtractor to provide the indexes
        Returns:
        true if this filter is enabled for all bits specified by the IndexExtractor

      • estimateN

        public int estimateN()
        Description copied from interface: BloomFilter
        Estimates the number of items in the Bloom filter.

        By default this is the rounding of the Shape.estimateN(cardinality) calculation for the shape and cardinality of this filter.

        This produces an estimate roughly equivalent to the number of Hashers that have been merged into the filter by rounding the value from the calculation described in the Shape class Javadoc.

        Note:

        • if cardinality == numberOfBits, then result is Integer.MAX_VALUE.
        • if cardinality > numberOfBits, then an IllegalArgumentException is thrown.
        Specified by:
        estimateN in interface BloomFilter<T extends BloomFilter<T>>
        Returns:
        an estimate of the number of items in the bloom filter. Will return Integer.MAX_VALUE if the estimate is larger than Integer.MAX_VALUE.
        See Also:
        Shape.estimateN(int), Shape

      • estimateUnion

        public int estimateUnion​(BloomFilter other)
        Description copied from interface: BloomFilter
        Estimates the number of items in the union of this Bloom filter with the other bloom filter.

        This produces an estimate roughly equivalent to the number of unique Hashers that have been merged into either of the filters by rounding the value from the calculation described in the Shape class Javadoc.

        estimateUnion should only be called with Bloom filters of the same Shape. If called on Bloom filters of differing shape this method is not symmetric. If other has more bits an IllegalArgumentException may be thrown.

        Specified by:
        estimateUnion in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        other - The other Bloom filter
        Returns:
        an estimate of the number of items in the union. Will return Integer.MAX_VALUE if the estimate is larger than Integer.MAX_VALUE.
        See Also:
        BloomFilter.estimateN(), Shape

      • find

        public int[] find​(BitMapExtractor bitMapExtractor)
        Finds the layers in which the BitMapExtractor is found.
        Parameters:
        bitMapExtractor - the BitMapExtractor to search for.
        Returns:
        an array of layer indices in which the Bloom filter is found.

      • find

        public int[] find​(BloomFilter bf)
        Finds the layers in which the Bloom filter is found.
        Parameters:
        bf - the Bloom filter to search for.
        Returns:
        an array of layer indices in which the Bloom filter is found.

      • find

        public int[] find​(Hasher hasher)
        Finds the layers in which the Hasher is found.
        Parameters:
        hasher - the Hasher to search for.
        Returns:
        an array of layer indices in which the Bloom filter is found.

      • find

        public int[] find​(IndexExtractor indexExtractor)
        Finds the layers in which the IndexExtractor is found.
        Parameters:
        indexExtractor - the Index extractor to search for.
        Returns:
        an array of layer indices in which the Bloom filter is found.

      • flatten

        public SimpleBloomFilter flatten()
        Create a standard (non-layered) Bloom filter by merging all of the layers. If the filter is empty this method will return an empty Bloom filter.
        Specified by:
        flatten in interface BloomFilterExtractor
        Returns:
        the merged bloom filter.

      • get

        public T get​(int depth)
        Gets the Bloom filter at the specified depth
        Parameters:
        depth - the depth of the filter to return.
        Returns:
        the Bloom filter at the specified depth.
        Throws:
        java.util.NoSuchElementException - if depth is not in the range [0,getDepth())

      • getDepth

        public final int getDepth()
        Gets the depth of the deepest layer. The minimum value returned by this method is 1.
        Returns:
        the depth of the deepest layer.

      • isEmpty

        public boolean isEmpty()
        Description copied from interface: BloomFilter
        Determines if all the bits are off. This is equivalent to cardinality() == 0.

        Note: This method is optimized for non-sparse filters. Implementers are encouraged to implement faster checks if possible.

        Specified by:
        isEmpty in interface BloomFilter<T extends BloomFilter<T>>
        Returns:
        true if no bits are enabled, false otherwise.

      • merge

        public boolean merge​(BitMapExtractor bitMapExtractor)
        Description copied from interface: BloomFilter
        Merges the specified hasher into this Bloom filter. Specifically all bit indexes that are identified by the bitMapExtractor will be enabled in this filter.

        Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain all the indexes enabled in the bitMapExtractor. This state may occur in complex Bloom filter implementations like counting Bloom filters.

        Specified by:
        merge in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        bitMapExtractor - The BitMapExtractor to merge.
        Returns:
        true if the merge was successful

      • merge

        public boolean merge​(BloomFilter bf)
        Description copied from interface: BloomFilter
        Merges the specified Bloom filter into this Bloom filter.

        Specifically all bit indexes that are identified by the other will be enabled in this filter.

        Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain the other Bloom filter. This state may occur in complex Bloom filter implementations like counting Bloom filters.

        Specified by:
        merge in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        bf - The bloom filter to merge into this one.
        Returns:
        true if the merge was successful

      • merge

        public boolean merge​(IndexExtractor indexExtractor)
        Description copied from interface: BloomFilter
        Merges the specified IndexExtractor into this Bloom filter. Specifically all bit indexes that are identified by the indexExtractor will be enabled in this filter.

        Note: This method should return true even if no additional bit indexes were enabled. A false result indicates that this filter may or may not contain all the indexes of the indexExtractor. This state may occur in complex Bloom filter implementations like counting Bloom filters.

        Specified by:
        merge in interface BloomFilter<T extends BloomFilter<T>>
        Parameters:
        indexExtractor - The IndexExtractor to merge.
        Returns:
        true if the merge was successful

      • processBitMaps

        public boolean processBitMaps​(java.util.function.LongPredicate predicate)
        Description copied from interface: BitMapExtractor
        Each bit map is passed to the predicate in order. The predicate is applied to each bit map value, if the predicate returns false the execution is stopped, false is returned, and no further bit maps are processed.

        If the extractor is empty this method will return true.

        Any exceptions thrown by the action are relayed to the caller.

        Specified by:
        processBitMaps in interface BitMapExtractor
        Parameters:
        predicate - the function to execute
        Returns:
        true if all bit maps returned true, false otherwise.

      • processBloomFilters

        public final boolean processBloomFilters​(java.util.function.Predicate<BloomFilter> bloomFilterPredicate)
        Processes the Bloom filters in depth order with the most recent filters first. Each filter is passed to the predicate in turn. The function exits on the first false returned by the predicate.
        Specified by:
        processBloomFilters in interface BloomFilterExtractor
        Parameters:
        bloomFilterPredicate - the predicate to execute.
        Returns:
        true if all filters passed the predicate, false otherwise.

      • processIndices

        public boolean processIndices​(java.util.function.IntPredicate predicate)
        Description copied from interface: IndexExtractor
        Each index is passed to the predicate. The predicate is applied to each index value, if the predicate returns false the execution is stopped, false is returned, and no further indices are processed.

        Any exceptions thrown by the action are relayed to the caller.

        Indices ordering and uniqueness is not guaranteed.

        Specified by:
        processIndices in interface IndexExtractor
        Parameters:
        predicate - the action to be performed for each non-zero bit index.
        Returns:
        true if all indexes return true from consumer, false otherwise.