alluxio.client.file.cache.cuckoofilter

Class CuckooUtils

java.lang.Object

alluxio.client.file.cache.cuckoofilter.CuckooUtils

public class CuckooUtils
extends java.lang.Object

This class provides some useful methods for cuckoo filters.

Constructor Summary

Constructors

Constructor and Description
CuckooUtils()

Method Summary

Modifier and Type	Method and Description
static int	altIndex(int index, int tag, int numBuckets) Compute the alternative index on given hash value and tag.
static int	indexHash(int hv, int numBuckets) Computes the bucket index on given hash value.
static int	optimalBitsPerTag(double fpp, double loadFactor) Compute the number of bits of each tag on given fpp.
static long	optimalBuckets(long expectedInsertions, double loadFactor, int tagsPerBucket) Compute the number of buckets using the expected number of insertions, the load factor, and the number of tags per bucket.
static int	tagHash(int hv, int bitsPerTag) Compute the fingerprint on given hash value.

Methods inherited from class java.lang.Object

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

Constructor Detail

CuckooUtils

public CuckooUtils()

Method Detail

indexHash

public static int indexHash(int hv,
                            int numBuckets)

Computes the bucket index on given hash value.

Parameters:

hv - the hash value

numBuckets - the number of buckets

Returns:

the bucket computed

altIndex

public static int altIndex(int index,
                           int tag,
                           int numBuckets)

Compute the alternative index on given hash value and tag.

Parameters:

index - the bucket index

tag - the fingerprint

numBuckets - the number of buckets

Returns:

the alternative bucket index computed

tagHash

public static int tagHash(int hv,
                          int bitsPerTag)

Compute the fingerprint on given hash value.

Parameters:

hv - the hash value

bitsPerTag - the number of bits each tag has

Returns:

the fingerprint

optimalBitsPerTag

public static int optimalBitsPerTag(double fpp,
                                    double loadFactor)

Compute the number of bits of each tag on given fpp. The equation is from "Cuckoo Filter: Practically Better Than Bloom" by Fan et al.

Parameters:

fpp - the false positive probability

loadFactor - the load factor

Returns:

the optimized number of bits

optimalBuckets

public static long optimalBuckets(long expectedInsertions,
                                  double loadFactor,
                                  int tagsPerBucket)

Compute the number of buckets using the expected number of insertions, the load factor, and the number of tags per bucket.

Parameters:

expectedInsertions - the expected number of unique items

loadFactor - the load factor

tagsPerBucket - the number of slots per bucket has

Returns:

the optimized number of buckets