| Title |
New Bloom Filter Structure Improves Processing Speed in Multiple Sets |
| DOI |
https://doi.org/10.5573/ieie.2021.58.8.17 |
| Keywords |
Bloom filter; multiple sets; membership query; false positives; accuracy |
| Abstract |
Membership query of multiple sets is used in various ways in network applications. When multiple sets membership query is performed using a standard Bloom filter, a Bloom filter of the same size as the number of a set must be used. This paper proposes a method to determine the set to which each element of multiple sets belongs by using a single Bloom filter with multi-bit. The proposed structure implements a Bloom filter with a cell size proportional to the number of multiple sets and proposes a structure that enables multiple sets membership query while reducing the operation of the Bloom filter through single programming and querying. Simulation result shows that false positive error decreased and accuracy increased as the sizing factor of the Bloom filter increased. In addition, it was confirmed that the processing speed of the Bloom filter operation decreases as the number of elements in the intersection increases. |