TY - GEN
T1 - Functional bloom filter, better than hash tables
AU - Byun, Hayoung
AU - Lim, Hyesook
N1 - Funding 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).
Publisher Copyright:
© 2018 Institute of Electronics and Information Engineers.
PY - 2018/4/2
Y1 - 2018/4/2
N2 - 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.
AB - 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.
KW - Bloom filter
KW - functional Bloom filter
KW - hash table
KW - key-value structure
UR - http://www.scopus.com/inward/record.url?scp=85048587837&partnerID=8YFLogxK
U2 - 10.23919/ELINFOCOM.2018.8330628
DO - 10.23919/ELINFOCOM.2018.8330628
M3 - Conference contribution
AN - SCOPUS:85048587837
T3 - International Conference on Electronics, Information and Communication, ICEIC 2018
SP - 1
EP - 3
BT - International Conference on Electronics, Information and Communication, ICEIC 2018
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 24 January 2018 through 27 January 2018
ER -