Class CuckooFilter

java.lang.Object
org.elasticsearch.common.util.CuckooFilter
All Implemented Interfaces:
Writeable

public class CuckooFilter
extends java.lang.Object
implements Writeable
An approximate set membership datastructure CuckooFilters are similar to Bloom Filters in usage; values are inserted, and the Cuckoo can be asked if it has seen a particular value before. Because the structure is approximate, it can return false positives (says it has seen an item when it has not). False negatives are not possible though; if the structure says it _has not_ seen an item, that can be trusted. The filter can "saturate" at which point the map has hit it's configured load factor (or near enough that a large number of evictions are not able to find a free slot) and will refuse to accept any new insertions. NOTE: this version does not support deletions, and as such does not save duplicate fingerprints (e.g. when inserting, if the fingerprint is already present in the candidate buckets, it is not inserted). By not saving duplicates, the CuckooFilter loses the ability to delete values. But not by allowing deletions, we can save space (do not need to waste slots on duplicate fingerprints), and we do not need to worry about inserts "overflowing" a bucket because the same item has been repeated repeatedly NOTE: this CuckooFilter exposes a number of Expert APIs which assume the caller has intimate knowledge about how the algorithm works. It is recommended to use SetBackedScalingCuckooFilter instead. Based on the paper: Fan, Bin, et al. "Cuckoo filter: Practically better than bloom." Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies. ACM, 2014. https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • Nested Class Summary

    Nested classes/interfaces inherited from interface org.elasticsearch.common.io.stream.Writeable

    Writeable.Reader<V>, Writeable.Writer<V>
  • Method Summary

    Modifier and Type Method Description
    boolean equals​(java.lang.Object other)  
    int getCount()
    Get the number of unique items that are being tracked
    long getSizeInBytes()  
    int hashCode()  
    void writeTo​(StreamOutput out)
    Write this into the StreamOutput.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, toString, wait, wait, wait
  • Method Details

    • writeTo

      public void writeTo​(StreamOutput out) throws java.io.IOException
      Description copied from interface: Writeable
      Write this into the StreamOutput.
      Specified by:
      writeTo in interface Writeable
      Throws:
      java.io.IOException
    • getCount

      public int getCount()
      Get the number of unique items that are being tracked
    • getSizeInBytes

      public long getSizeInBytes()
    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class java.lang.Object
    • equals

      public boolean equals​(java.lang.Object other)
      Overrides:
      equals in class java.lang.Object