Popularity Cuckoo Filter: Always Keeping Popular Items in Mind

A Bloom Filter is a basic and randomized means of storing information that can accurately determine membership status queries with no false negatives and a small probability of false positives. As its improvement, a Cuckoo Filter is a kind of new data structure which can support adding, removing items dynamically and achieving higher performance than a Bloom Filter. But current Cuckoo filters usually handle items assuming they have the same possibility to be queried, and treat them without difference, which is unable to satisfy the demand for querying that most popular items in dataset, such as in web caching. We propose a new data structure called the popularity cuckoo filter that can make false positive smaller and prioritize storing members with higher popularity. Popularity cuckoo filters use different numbers of hash functions for items with different popularities, so they have better space efficiencies. Our experimental results show that the popularity cuckoo filter can distinguish items with large or small popularities well and suit datasets with irregular query patterns and non-uniform membership likelihood.