Constant-Weight Group Coded Bloom Filter for Multiple-Set Membership Queries

Multiple-set membership query problem plays a very important role in many network systems, including packet forwarding architectures in big data centers, routing switching devices and internet firewall systems. Many solutions to multiple-set membership query problem are based on Bloom filters. And each of these solutions has its own merits. Some have high query speed and some have good accuracy. But generally, they cannot have both at the same time. In this paper, we propose a probabilistic data structure named constant-weight group coded Bloom Filter (CWGCBF) for fast and accurate multi-set membership query. The key technique in CWGCBF is encoding each element’s set ID to constant weight code, and directly recording this constant-weight code in the bloom filter vector. Experimental results show that in terms of false positive ratio, CWGCBF, Shifting Bloom Filter and Combinatorial Bloom Filter have great advantages to the other compared Bloom filters, and in terms of time efficiency, CWGCBF and ID Bloom Filter are several times faster than the others.