Magic Cube Bloom Filter: Answering Membership Queries for Multiple Sets

Given $d$ sets without intersection, the multi-set membership query problem is to decide which set an incoming item $e$ belongs to. Multi-set membership query is a fundamental problem in a variety of fields of computer science, especially computer networking. Although several approaches have been proposed in the literature to address this problem, they cannot achieve a high processing speed, a high accuracy, and a small memory usage at the same time. In this paper, we propose a novel data structure, namely Magic Cube Bloom Filter (MCBF), which outperforms the state-of-the-art in terms of accuracy and query speed with a limited memory usage. The key idea of the Magic Cube Bloom filter is that items from the same set are stored in different Bloom filters, improving the accuracy by the redistribution of items. The MC-BF also improves the query speed by utilizing spatial locality. Experimental results show that the MC-BF outperforms the state-of-the-art BUFFALO by up to 148.5 times in terms of accuracy, and up to 3.16 times in terms of query speed. We have made the source code of our MC-BF available on Github [1].