TY - GEN
T1 - Cuckoo bloom filter
AU - Mun, Ju Hyoung
AU - Lim, Hyesook
N1 - Funding Information:
ACKNOWLEDGMENT This research was supported by a National Research Foundation of Korea (NRF), 2017R1A2B4011254.
Publisher Copyright:
© 2019 Institute of Electronics and Information Engineers (IEIE).
PY - 2019/5/3
Y1 - 2019/5/3
N2 - A membership identification is a key functionality in many network applications. Various data structures have been introduced in order to support the efficient membership identification. Since a Bloom filter can provide simple but efficient membership checking, it is widely used in many network applications. However, the query results of Bloom filters can have false positives, which can degrade the search performance. Thus, reducing false positives of Bloom filters is challenging. In order to reduce the false positive rate, this paper proposes to use two sets of hash functions: primary and secondary. When the cell referenced by the primary hash function is occupied, the value of that cell is relocated to a cell referenced by the secondary hash functions like in the cuckoo hash. The proposed structure is evaluated using various sets, and the simulation results show that the proposed scheme can reduce the false positive rates.
AB - A membership identification is a key functionality in many network applications. Various data structures have been introduced in order to support the efficient membership identification. Since a Bloom filter can provide simple but efficient membership checking, it is widely used in many network applications. However, the query results of Bloom filters can have false positives, which can degrade the search performance. Thus, reducing false positives of Bloom filters is challenging. In order to reduce the false positive rate, this paper proposes to use two sets of hash functions: primary and secondary. When the cell referenced by the primary hash function is occupied, the value of that cell is relocated to a cell referenced by the secondary hash functions like in the cuckoo hash. The proposed structure is evaluated using various sets, and the simulation results show that the proposed scheme can reduce the false positive rates.
UR - http://www.scopus.com/inward/record.url?scp=85065870224&partnerID=8YFLogxK
U2 - 10.23919/ELINFOCOM.2019.8706343
DO - 10.23919/ELINFOCOM.2019.8706343
M3 - Conference contribution
AN - SCOPUS:85065870224
T3 - ICEIC 2019 - International Conference on Electronics, Information, and Communication
BT - ICEIC 2019 - International Conference on Electronics, Information, and Communication
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 18th International Conference on Electronics, Information, and Communication, ICEIC 2019
Y2 - 22 January 2019 through 25 January 2019
ER -