The Logarithmic Dynamic Cuckoo Filter

The emergence of big data applications makes efficient representation for large-scale dynamic data sets a challenge. The state-of-the-art design, i.e., the dynamic cuckoo filter (DCF), provides extensible approximate set representation by employing a novel chain based data structure which allows appending new building cuckoo filter blocks. However, such a design needs linearly increasing computation costs and memory space when a set scales. This makes it inefficient for big data sets. In this paper, we propose a novel data structure for dynamic big data sets, called logarithmic dynamic cuckoo filter (LDCF). LDCF uses a novel multi-level tree structure and reduces the worst insertion and membership testing times from O(N) to O(1), where N is the size of the set. At the same time, LDCF reduces the memory cost of DCF as the cardinality of the set increases. Comprehensive experiment results show that LDCF significantly reduces the membership checking time and the memory space cost for large-scale datasets compared to state-of-the-art designs.