SLCF: Single-hash lookup cuckoo filter

摘要

Approximate Membership Query (AMG) data structures are widely used in the networking area recently. The most popular AMQ data structures are Bloom, Quotient and Cuckoo Filter (CF). The CF is more efficient than the Quotient and Bloom filters in term of the lookup time and false positive rate. An issue in CF is utilization of two hash functions in the query phase that increases the lookup time. Another issue is the relocation loop problem in the programming phase that attempts to find an empty bucket for the collied items. In this paper, a new approach called Single-hash Lookup Cuckoo Filter (SLCF) using one hash function to lookup an item is proposed. In the programming phase, SLCF utilizes a sequence of hash functions without any relocation to find an empty bucket and storing the overflowed items. It finds a bucket with an empty place and sets an index in the original bucket to the address of found bucket. To accelerate the query phase, a handle as a tiny part of the fingerprint is placed in conjunction with the index value in the bucket. In the query phase, only one hash function is used and if the queried item cannot be found in the bucket, the handle is investigated to membership checking. Otherwise, the second bucket pointed by the index is accessed. The simulation results for name search in the named data networking demonstrate that the lookup time is improved 27% for 16 million names in comparison to CF.