Tongxin xuebao (Mar 2016)
CBFM:cutted Bloom filter matrix for multi-dimensional membership query
Abstract
In order to improve the flexibility and accuracy of mu i-dimensional membership query,a new indexing structure called CBFM(cutted Bloom filter matrix)was proposed.CBFM built the bit matrix by the Cartesian product of different bloom filters,each representing one attribute of primary data.In this way,the proposed matrix supported by-attribute membership query.Besides,the attribute combinations in the bit matrix could be reduced and weighted on demand to further enhance memory utilization rate.Theoretical analysis proves that CBFM utilizes memory more effi-ciently than BFM,the current state of art.Experiments also show that,on the scenario of memory size fixed,the false positive rate of CBFM is lower than that of all other indexin ethods.Especially on the scenario of memory constrained,the false positive rate of CBFM can be 3 orders of magnitude lower than that of BFM(Bloom filter matrix) indexing me-thod.CBFM is an accurate data structure for multi-dimensional membership query.
