The Design And Application Of Dynamic Cuckoo Filter

The emergence of large-scale dynamic sets in real applications creates stringent requirements for approximate set representation structures: 1)the capacity of the set representation structures should support flexibly extending or reducing to cope with dynamically changing of set size;2)the set representation structures should support reliable delete operation.Existing techniques for approximate set representation,e.g.,the Cuckoo filter,the Bloom filter and its variants cannot meet both the requirements of a dynamic set.To solve the problem,in this paper we propose the dynamic Cuckoo filter(DCF)to support reliable delete operation and elastic capacity for dynamic set representation and membership testing.The dynamic Cuckoo filter achieves dynamic capacity by appending building blocks dynamically,solves the problem of low space utilization by solving by the relocation technology based on the idea of ‘The power of two choices' and leverages fingerprints to identify data existence,further ensures the reliable deletion operation.Two factors contribute to the efficiency of the dynamic Cuckoo filter design.First,the data structure of a dynamic Cuckoo filter is extendable,making the representation of a dynamic set space efficient.Second,a dynamic Cuckoo filter utilizes a monopolistic fingerprint for representing an item and guarantees reliable delete operation.Experiment results show that compared to the existing state-of-the-art designs,dynamic Cuckoo filter achieves 75% reduction in memory cost,50% improvement in construction speed,and 80% improvement in speed of membership query.We implement a prototype file backup system and use dynamic Cuckoo filter for data deduplication.Comprehensive experiment results demonstrate the efficiency of our dynamic Cuckoo filter design compared to existing schemes.