com.duprasville.guava.probably

Enum CuckooStrategies

java.lang.Object

java.lang.Enum<CuckooStrategies>

com.duprasville.guava.probably.CuckooStrategies

All Implemented Interfaces:

Serializable, Comparable<CuckooStrategies>

public enum CuckooStrategies
extends Enum<CuckooStrategies>

Collections of strategies of generating the f-bit fingerprint, index i1 and index i2 required for an element to be mapped to a CuckooTable of m buckets with hash function h. These strategies are part of the serialized form of the Cuckoo filters that use them, thus they must be preserved as is (no updates allowed, only introduction of new versions).

Important: the order of the constants cannot change, and they cannot be deleted - we depend on their ordinal for CuckooFilter serialization.

Author:

Brian Dupras

Enum Constant Summary

Enum Constants

Enum Constant and Description
MURMUR128_BEALDUPRAS_32 Adaptation of "Cuckoo Filter: Practically Better Than Bloom", Bin Fan, et al, that is comparable to a Bloom Filter's memory efficiency, supports entry deletion, and can accept up to 12.8 billion entries at 3% FPP.

Method Summary

Methods

Modifier and Type	Method and Description
abstract com.duprasville.guava.probably.CuckooStrategy	strategy()
static CuckooStrategies	valueOf(String name) Returns the enum constant of this type with the specified name.
static CuckooStrategies[]	values() Returns an array containing the constants of this enum type, in the order they are declared.

Methods inherited from class java.lang.Enum

clone, compareTo, equals, finalize, getDeclaringClass, hashCode, name, ordinal, toString, valueOf

Methods inherited from class java.lang.Object

getClass, notify, notifyAll, wait, wait, wait

Enum Constant Detail

MURMUR128_BEALDUPRAS_32

public static final CuckooStrategies MURMUR128_BEALDUPRAS_32

Adaptation of "Cuckoo Filter: Practically Better Than Bloom", Bin Fan, et al, that is comparable to a Bloom Filter's memory efficiency, supports entry deletion, and can accept up to 12.8 billion entries at 3% FPP.

This strategy uses 32 bits of Hashing.murmur3_128(int) to find an entry's primary index. The next non-zero f-bit segment of the hash is used as the entry's fingerprint. An entry's alternate index is defined as [hash(fingerprint) * parsign(index)] modulo bucket_count, where hash(fingerprint) is always odd, and parsign(index) is defined as +1 when index is even and -1 when index is odd. The filter's bucket count is rounded up to an even number. By specifying an even number of buckets and an odd fingerprint hash, the parity of the alternate index is guaranteed to be opposite the parity of the primary index. The use of the index's parity to apply a sign to hash(fingerprint) causes the operation to be reversible, i.e. index(e) == altIndex(altIndex(e)).

A notable difference of this strategy from "Cuckoo Filter" is the method of selecting an entry's alternate index. In the paper, the alternate index is defined as index xor hash(fingerprint). The use of xor requires that the index space be defined as [0..2^f]. The side-effect of this is that the Cuckoo Filter's bucket count must be a power of 2, meaning the memory utilization of the filter must be "rounded up" to the next power of two. This side-effect of the paper's algorithm is avoided by the algorithm as described above.

Method Detail

values

public static CuckooStrategies[] values()

Returns an array containing the constants of this enum type, in the order they are declared. This method may be used to iterate over the constants as follows:

for (CuckooStrategies c : CuckooStrategies.values())
    System.out.println(c);

Returns:

an array containing the constants of this enum type, in the order they are declared

valueOf

public static CuckooStrategies valueOf(String name)

Returns the enum constant of this type with the specified name. The string must match exactly an identifier used to declare an enum constant in this type. (Extraneous whitespace characters are not permitted.)

Parameters:

name - the name of the enum constant to be returned.

Returns:

the enum constant with the specified name

Throws:

IllegalArgumentException - if this enum type has no constant with the specified name

NullPointerException - if the argument is null

strategy

public abstract com.duprasville.guava.probably.CuckooStrategy strategy()