Abstract
A Bloom filter is a simple data structure that identifies the membership of an input against a given set. Various types of Bloom filters have been widely used in recent years. While standard Bloom filters only provide the membership identification of a given set by storing a value of 0 or 1 in a cell, we propose to provide the membership information of multiple sets through a single Bloom filter by storing different values in a cell. In other words, if two different sets are given, the proposed Bloom filter structure allocates 2 bits in one cell, and two different values indicating each set are specified in advance to program the sets. Hence the proposed Bloom filter structure accurately determines the membership of each set and the intersection of two sets by querying a single Bloom filter. In addition, we propose a circled Bloom filter structure to improve the accuracy of the membership identification. Experimental results show that the proposed Bloom filter structure provides the better accuracy with using the half of querying operations compared to two separate Bloom filter structure.
Original language | English |
---|---|
Title of host publication | ICEIC 2019 - International Conference on Electronics, Information, and Communication |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
ISBN (Electronic) | 9788995004449 |
DOIs | |
State | Published - 3 May 2019 |
Event | 18th International Conference on Electronics, Information, and Communication, ICEIC 2019 - Auckland, New Zealand Duration: 22 Jan 2019 → 25 Jan 2019 |
Publication series
Name | ICEIC 2019 - International Conference on Electronics, Information, and Communication |
---|
Conference
Conference | 18th International Conference on Electronics, Information, and Communication, ICEIC 2019 |
---|---|
Country/Territory | New Zealand |
City | Auckland |
Period | 22/01/19 → 25/01/19 |
Bibliographical note
Funding Information:ACKNOWLEDGMENT This research was supported by a National Research Foundation of Korea (NRF), 2018R1A6A3A11040736 and 2017R1A2B4011254.
Publisher Copyright:
© 2019 Institute of Electronics and Information Engineers (IEIE).
Keywords
- Bloom filter
- Circle
- Double-meaning
- Intersection