CECF: The Concurrent Entry-extensible Cuckoo Filter

Abstract

The emergence of huge and dynamic datasets in practical applications poses significant challenges for approximate set representation structures. The cardinality of these sets fluctuates, there’s a growing demand for adaptable and flexible representation structures. The existing dynamic representation structures offer filter-level and entry-level extensions Cuckoo Filter. The entry-level extension Cuckoo Filter, E2CF, achieves this by leveraging adjacent buckets with contiguous physical addresses within the Cuckoo Filter to extend bucket entries, avoids many discrete memory accesses in a query. However, for big data processing, a set representation structure may be read and inserted frequently, and query operations may be performed at the same time as the insertion. Since the E2CF insert may have a relocation process, reading this item will fail. Therefore, this paper proposes a multi-core concurrent E2CF (CECF). CECF utilizes path lock table to store the path of the inserting item. Experimental results demonstrate that, when compared to the exising designs, CECF significantly reduces query and insertion times by 59% and 55%, respectively.