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.
|Title of host publication||International Conference on Electronics, Information and Communication, ICEIC 2018|
|Publisher||Institute of Electrical and Electronics Engineers Inc.|
|Number of pages||3|
|State||Published - 2 Apr 2018|
|Event||17th International Conference on Electronics, Information and Communication, ICEIC 2018 - Honolulu, United States|
Duration: 24 Jan 2018 → 27 Jan 2018
|Name||International Conference on Electronics, Information and Communication, ICEIC 2018|
|Conference||17th International Conference on Electronics, Information and Communication, ICEIC 2018|
|Period||24/01/18 → 27/01/18|
Bibliographical noteFunding Information:
This research was supported by the National Research Foundation of Korea (NRF), NRF-2014R 1A2A1A11051762, NRF-2015R1A2A1A15054081, and NRF-2017R1A2B4011254. This research was also supported by the Ministry of Science, ICT and Future Planning (MSIP), Korea, under the Information Technology Research Center (ITRC) support program (IITP-2017-2012-0-00559) supervised by the Institute for Information & communications Technology Promotion (IITP).
© 2018 Institute of Electronics and Information Engineers.
- Bloom filter
- functional Bloom filter
- hash table
- key-value structure