Advanced Micro Devices, Inc.
CUCKOO FILTERS AND CUCKOO HASH TABLES WITH BIASING, COMPRESSION, AND DECOUPLED LOGICAL SPARSITY

Abstract:

A method includes, for each key of a plurality of keys, identifying from a set of buckets a first bucket for the key based on a first hash function, and identifying from the set of buckets a second bucket for the key based on a second hash function. An entry for the key is stored in a bucket selected from one of the first bucket and the second bucket. The entry is inserted in a sequence of entries in a memory block. A position of the entry in the sequence of entries corresponds to the selected bucket. For each bucket in the set of buckets, an indication of a number of entries in the bucket is recorded.