A circled Bloom filter for the membership identification of multiple sets

Jungwon Lee, Hyesook Lim

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

4 Scopus citations

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 languageEnglish
Title of host publicationICEIC 2019 - International Conference on Electronics, Information, and Communication
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9788995004449
DOIs
StatePublished - 3 May 2019
Event18th International Conference on Electronics, Information, and Communication, ICEIC 2019 - Auckland, New Zealand
Duration: 22 Jan 201925 Jan 2019

Publication series

NameICEIC 2019 - International Conference on Electronics, Information, and Communication

Conference

Conference18th International Conference on Electronics, Information, and Communication, ICEIC 2019
Country/TerritoryNew Zealand
CityAuckland
Period22/01/1925/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

Fingerprint

Dive into the research topics of 'A circled Bloom filter for the membership identification of multiple sets'. Together they form a unique fingerprint.

Cite this