Paper Info
Title
CFBF: Reducing the Insertion Time of Cuckoo Filters With an Integrated Bloom Filter
Abstract
Cuckoo filters (CFs) are an alternative to Bloom filters (BFs) that supports deletions and can often be configured to have a lower false positive rate. A drawback of cuckoo filters is that the insertion process is complex and requires a large number of memory accesses when the filter operates at high occupancy. Therefore, insertion complexity may limit the applicability of cuckoo filters in many networking applications that require fast updates of the filter contents. In this letter, the cuckoo filter is extended to integrate a Bloom filter that is used to improve the performance of insertions. The proposed CFBF does not require additional memory accesses for lookup operations and preserves the support for deletion of the original cuckoo filter. The CFBF targets hardware implementations where the Bloom filter can be checked with negligible cost and where the memory width can also be adjusted to the bucket size. The evaluation results show that it can be used to reduce worst case insertion time by a factor of ten and achieve an average insertion time similar to that of a lookup. The CFBF can support bursts of hundreds of insertions for large filters and moderate false positive rates. Therefore, it can enable the use of hardware implemented cuckoo filters in applications that need to support bursts of insertions or to provide a low worst case insertion time.
Year
DOI
Venue
2019
10.1109/LCOMM.2019.2930508
IEEE Communications Letters
Keywords
Field
DocType
Hardware,Memory management,Complexity theory,Security,Software,Limiting,Logic gates
False positive rate,Bloom filter,Logic gate,Hardware implementations,Cuckoo,Computer science,Algorithm,Real-time computing,Software,Memory management,Insertion time
Journal
Volume
Issue
ISSN
23
10
1089-7798
Citations 
PageRank 
References 
1
0.36
0
Authors
3
Name
Order
Citations
PageRank
Pedro Reviriego152775.56
Jorge A. Martinez2102.64
Salvatore Pontarelli336854.05