Functional bloom filter, better than hash tables

Hayoung Byun, Hyesook Lim

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

Hash tables have been widely used in many applications, which need to return values corresponding to each input key. However, hash-based data structures have an intrinsic problem of collision, where different keys have the same index of a hash table. As the load factor of the hash table increases, the number of collisions increases. Elements that could not be stored because of the collision cause failures in returning values. Variant structures such as multi-hashing, cuckoo hashing, and d-left hashing have been studied, but none of the structures solve completely the collision problem. In this paper, we claim that a functional Bloom filter can replace a hash table. While the hash table requires to store each input key itself or the signature of each input key in addition to the return value, the functional Bloom filter can store the return value only, since different combinations of Bloom filter indexes can work as the signature of each input key. Performance evaluation results show that the functional Bloom filter is more efficient than hash-based data structures in storing more number of elements into a fixed size memory and hence in producing less failures.

Original languageEnglish
Title of host publicationInternational Conference on Electronics, Information and Communication, ICEIC 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1-3
Number of pages3
ISBN (Electronic)9781538647547
DOIs
StatePublished - 2 Apr 2018
Event17th International Conference on Electronics, Information and Communication, ICEIC 2018 - Honolulu, United States
Duration: 24 Jan 201827 Jan 2018

Publication series

NameInternational Conference on Electronics, Information and Communication, ICEIC 2018
Volume2018-January

Conference

Conference17th International Conference on Electronics, Information and Communication, ICEIC 2018
Country/TerritoryUnited States
CityHonolulu
Period24/01/1827/01/18

Keywords

  • Bloom filter
  • functional Bloom filter
  • hash table
  • key-value structure

Fingerprint

Dive into the research topics of 'Functional bloom filter, better than hash tables'. Together they form a unique fingerprint.

Cite this