Comparison on Search Failure between Hash Tables and a Functional Bloom Filter
Hash-based data structures have been widely used in many applications. An intrinsic problem of hashing is collision, in which two or more elements are hashed to the same value. If a hash table is heavily loaded, more collisions would occur. Elements that could not be stored in a hash table because o...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-07-01
|
| Series: | Applied Sciences |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2076-3417/10/15/5218 |
| _version_ | 1797560961932984320 |
|---|---|
| author | Hayoung Byun Hyesook Lim |
| author_facet | Hayoung Byun Hyesook Lim |
| author_sort | Hayoung Byun |
| collection | DOAJ |
| description | Hash-based data structures have been widely used in many applications. An intrinsic problem of hashing is collision, in which two or more elements are hashed to the same value. If a hash table is heavily loaded, more collisions would occur. Elements that could not be stored in a hash table because of the collision cause search failures. Many variant structures have been studied to reduce the number of collisions, but none of the structures completely solves the collision problem. In this paper, we claim that a functional Bloom filter (FBF) provides a lower search failure rate than hash tables, when a hash table is heavily loaded. In other words, a hash table can be replaced with an FBF because the FBF is more effective than hash tables in the search failure rate in storing a large amount of data to a limited size of memory. While hash tables require to store each input key in addition to its return value, a functional Bloom filter stores return values without input keys, because different index combinations according to each input key can be used to identify the input key. In search failure rates, we theoretically compare the FBF with hash-based data structures, such as multi-hash table, cuckoo hash table, and <i>d</i>-left hash table. We also provide simulation results to prove the validity of our theoretical results. The simulation results show that the search failure rates of hash tables are larger than that of the functional Bloom filter when the load factor is larger than 0.6. |
| first_indexed | 2024-03-10T18:07:44Z |
| format | Article |
| id | doaj.art-03cf5960885741669e62bb5123b12d53 |
| institution | Directory Open Access Journal |
| issn | 2076-3417 |
| language | English |
| last_indexed | 2024-03-10T18:07:44Z |
| publishDate | 2020-07-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Applied Sciences |
| spelling | doaj.art-03cf5960885741669e62bb5123b12d532023-11-20T08:19:31ZengMDPI AGApplied Sciences2076-34172020-07-011015521810.3390/app10155218Comparison on Search Failure between Hash Tables and a Functional Bloom FilterHayoung Byun0Hyesook Lim1Department of Electronic and Electrical Engineering, Ewha Womans University, Seoul 03760, KoreaDepartment of Electronic and Electrical Engineering, Ewha Womans University, Seoul 03760, KoreaHash-based data structures have been widely used in many applications. An intrinsic problem of hashing is collision, in which two or more elements are hashed to the same value. If a hash table is heavily loaded, more collisions would occur. Elements that could not be stored in a hash table because of the collision cause search failures. Many variant structures have been studied to reduce the number of collisions, but none of the structures completely solves the collision problem. In this paper, we claim that a functional Bloom filter (FBF) provides a lower search failure rate than hash tables, when a hash table is heavily loaded. In other words, a hash table can be replaced with an FBF because the FBF is more effective than hash tables in the search failure rate in storing a large amount of data to a limited size of memory. While hash tables require to store each input key in addition to its return value, a functional Bloom filter stores return values without input keys, because different index combinations according to each input key can be used to identify the input key. In search failure rates, we theoretically compare the FBF with hash-based data structures, such as multi-hash table, cuckoo hash table, and <i>d</i>-left hash table. We also provide simulation results to prove the validity of our theoretical results. The simulation results show that the search failure rates of hash tables are larger than that of the functional Bloom filter when the load factor is larger than 0.6.https://www.mdpi.com/2076-3417/10/15/5218Bloom filterhash tablefunctional Bloom filterkey-value data structuresearch failureload factor |
| spellingShingle | Hayoung Byun Hyesook Lim Comparison on Search Failure between Hash Tables and a Functional Bloom Filter Applied Sciences Bloom filter hash table functional Bloom filter key-value data structure search failure load factor |
| title | Comparison on Search Failure between Hash Tables and a Functional Bloom Filter |
| title_full | Comparison on Search Failure between Hash Tables and a Functional Bloom Filter |
| title_fullStr | Comparison on Search Failure between Hash Tables and a Functional Bloom Filter |
| title_full_unstemmed | Comparison on Search Failure between Hash Tables and a Functional Bloom Filter |
| title_short | Comparison on Search Failure between Hash Tables and a Functional Bloom Filter |
| title_sort | comparison on search failure between hash tables and a functional bloom filter |
| topic | Bloom filter hash table functional Bloom filter key-value data structure search failure load factor |
| url | https://www.mdpi.com/2076-3417/10/15/5218 |
| work_keys_str_mv | AT hayoungbyun comparisononsearchfailurebetweenhashtablesandafunctionalbloomfilter AT hyesooklim comparisononsearchfailurebetweenhashtablesandafunctionalbloomfilter |