Comparison on search failure between hash tables and a functional Bloom filter

Hayoung Byun, Hyesook Lim

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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 d-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.

Original languageEnglish
Article number5218
JournalApplied Sciences (Switzerland)
Volume10
Issue number15
DOIs
StatePublished - Aug 2020

Keywords

  • Bloom filter
  • Functional Bloom filter
  • Hash table
  • Key-value data structure
  • Load factor
  • Search failure

Fingerprint

Dive into the research topics of 'Comparison on search failure between hash tables and a functional Bloom filter'. Together they form a unique fingerprint.

Cite this