A Cuckoo Filter Modification Inspired by Bloom Filter
Probabilistic data structures are so popular in membership queries, network applications, and so on. Bloom Filter and Cuckoo Filter are two popular space efficient models that incorporate in set membership checking part of many important protocols. They are compact representation of data that use ha...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Amirkabir University of Technology
2019-12-01
|
| Series: | AUT Journal of Electrical Engineering |
| Subjects: | |
| Online Access: | https://eej.aut.ac.ir/article_3589_d258037f1f9be50a1208ba86323a2857.pdf |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Probabilistic data structures are so popular in membership queries, network applications, and so on. Bloom Filter and Cuckoo Filter are two popular space efficient models that incorporate in set membership checking part of many important protocols. They are compact representation of data that use hash functions to randomize a set of items. Being able to store more elements while keeping a reasonable false positive probability is a key factor of design. A new algorithm is proposed to improve some of the performance properties of Cuckoo Filter such as false positive rate and insertion performance and solve some drawbacks of the Cuckoo algorithm such as endless loop. Main characteristic of the Bloom Filter is used to improve Cuckoo Filter, so we have a smart Cuckoo Filter which is modified by Bloom Filter (SCFMBF). SCFMBF uses the same table of buckets as Cuckoo Filter but instead of storing constant Fingerprints, It stores Bloom Filters. Bloom Filters can be accumulated in the table’s buckets which leads to higher insertion feasibility. We also address the endless loop problem of Cuckoo Filter that means an inserted item is stuck in an iterative process of finding an empty bucket, so a smart algorithm is designed which not only solves endless loop problems but also prevents insertion failure. our algorithm prevents double checking of a bucket and avoids making loops. Consequently the capacity of SCFMBF is improved significantly. Results of comparison with Cuckoo Filter shows that false positive probability of SCFMBF method is four times enhanced. |
|---|---|
| ISSN: | 2588-2910 2588-2929 |