CBFM：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法

doi:10.11959/j.issn.1000-436x.2016061

Abstract

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.

Key words: query algorithm, multi-dimensional membership query, Bloom filter, bit matrix

Yong WANG,Xiao-chun YUN,ANGShu-peng WANG,Xi WANG. CBFM:cutted Bloom filter matrix for multi-dimensional membership query[J]. Journal on Communications, 2016, 37(3): 139-147.

Figures/Tables 15

参数	定义
d	数据集的属性个数
n	数据集期望元素个数
e	整体期望误判率
	删减的维度组合数目，每个属性组合包含 r_i个属性
c	$i \in R, 1 \leq i \leq c, \sum_{i = 1}^{c} r_{i} \leq d$
m	单属性位向量大小
M	总体内存空间占用

References 19

[1]	LYNCH C . Big data:how do your data grow[J]. Nature, 2008,455(7209): 28-29.
[2]	CHANG F , DEAN J , GHEMAWAT S , et al. Bigtable:a distributed storage system for structured data[J]. ACM Transactions on Computer Systems(TOCS), 2008,26(2): 4.
[3]	VORA M N . Hadoop-HBase for large-scale data[J]. IEEE Computer Science and Network Technology, 2011,(1): 601-605.
[4]	DEAN J , GHEMAWAT S . MapReduce:simplified data processing on large clusters[J]. Communications of the ACM, 2008,51(1): 107-113.
[5]	THUSOO A , SARMA J S , JAIN N , et al. Hive:a warehousin solu-tion over a map-reduce framework[J]. Proceedings of the VLDB Endowment, 2009,2(2): 1626-1629.
[6]	KORNACKER M , BEHM A , BITTORF V , et al. Impala:a modern,open-source SQL engine for Hadoop[C]. Conference on Innovative Data Systems Research(CIDR'15). c2015.
[7]	TARKOMA S , ROTHENBERG C E , LAGERSPETZ E . Theory and practice of bloom filters for distributed systems[J]. Communications Surveys ＆ Tutorials,IEEE, 2012,14(1): 131-144.
[8]	RODEH O , TEPERMAN A , zFS-a scalable distributed file system using object disks[C]// Mass Storage Systems and Technologies(MSST), c2003:207-218.
[9]	DEBNATH B , SENGUPTA S , LI J . FlashStore:high throughput per-sistent key-value store[J]. Proceedings of the VLDB Endowment, 2010,3(1-2): 1414-1425.
[10]	ZHOU X , ZHANG X , WANG Y , et al. Efficient distributed mul-ti-dimensional index for big data management[M]. Springer Berlin Heidelberg, 2013.130-141.
[11]	NISHIMURA S , DAS S , AGRAWAL D , et al. MD-HBase:a scalable multi-dimensional data infrastructure for location aware services[J]. IEEE Mobile Data Management(MDM), 2011,1:7-16.
[12]	BLOOM B H . Space/time trade-offs in hash coding with allowable errors[J]. Communications of the ACM, 1970,13(7): 422-426.
[13]	GUO D , WU J , CHEN H , et al. Theory and network applications of dynamic bloom filters[C]// INFOCOM. c2006:1-12.
[14]	谢鲲，秦拯，文吉刚，等. 联合多维布鲁姆过滤器查询算法[J]. 通信学报， 2008,29(1): 56-64. XIE K , QIN Z , WEN J G , et al. Combine multi-dimension Bloom filter for membership queries[J]. Journal on Communications, 2008,29(1): 56-64.
[15]	WANG Z , LUO T , XU G , et al. A new indexing technique for support-ing by-attribute membership query of multidimensional data[M]. Springer Berlin Heidelberg. 2013:266-277.
[16]	WANG Z , LUO T , XU G , et al. The application of cartesian-join of bloom filters to supporting membership query of multid mensional data[C]// IEEE Big Data. c2014:288-295.
[17]	BRODER A , MITZENMACHER M . Network applications of bloom filters:a survey[J]. Internet Mathematics(MDM), 2004,1(4): 485-509.
[18]	CHENG X , LI H , WANG Y , et al. BF-matrix:a secondary index for the cloud storage[M]. Springer International Publishing. 2014:384-396.
[19]	CRAINICEANU A , LEMIRE D . Bloofi:multidimensional Bloom filters[J]. Information Systems, 2015,54:311-324.

Metrics

Recommended 0

No Suggested Reading articles found!

e	d	c	n(BFM)	n(CBFM)
10^{- 1}	3	2(0x5,0x3)	42	604
10^{- 2}	3	2(0x5,0x3)	21	302
10^{- 3}	3	2(0x5,0x3)	14	201
10^{- 4}	3	2(0x5,0x3)	10	151
10^{- 5}	3	2(0x5,0x3)	8	121

e	d	c	M-BFM/MB	M-CBFM/MB
10^{- 1}	3	2(0x5,0x3)	13 125.00	2.74
10^{- 2}	3	2(0x5,0x3)	105 007.00	10.96
10^{- 3}	3	2(0x5,0x3)	354 328.05	24.65
10^{- 4}	3	2(0x5,0x3)	839 932.53	43.81
10^{- 5}	3	2(0x5,0x3)	1 640 339.20	68.46

CBFM:cutted Bloom filter matrix for multi-dimensional membership query

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 19

Related Articles 15

Metrics

Recommended 0

[1]	Dongmei YANG, Yue CHEN, Jianghong WEI, Xuexian HU. Identity-based puncturable signature scheme [J]. Journal on Communications, 2021, 42(12): 17-26.
[2]	Sheng WAN,Yuan-yuan HE,Feng-hua LI,Ben NIU,Hui LI,Xin-yu WANG. Bloom filter-based lightweight private matching scheme [J]. Journal on Communications, 2015, 36(12): 151-162.
[3]	. Research on simple query algorithm during mobile terminal disconnection [J]. Journal on Communications, 2014, 35(3): 23-207.
[4]	Ru-bing LIANG,Qiong LIU. Research on simple query algorithm during mobile terminal disconnection [J]. Journal on Communications, 2014, 35(3): 201-207.
[5]	Ying HOU,Yun-fei GUO,Hai HUANG,Kai WANG. Early traffic sampling algorithm based on SSCBF [J]. Journal on Communications, 2014, 35(10): 117-126.
[6]	. Early traffic sampling algorithm based on SSCBF [J]. Journal on Communications, 2014, 35(10): 14-126.
[7]	Fei XIANG,Chuan-yi LIU,Bin-xing FANG,Chun-lu WANG,HONGRui-ming Z. Research on ciphertext search for the cloud environment [J]. Journal on Communications, 2013, 34(7): 143-153.
[8]	. Research on ciphertext search for the cloud environment [J]. Journal on Communications, 2013, 34(7): 16-153.
[9]	Zhen ZHANG,Bin-qiang WANG,Feng-yu ZHANG,Ning-ning LIANG. Traffic measurement algorithm based on least recent used and Bloom filter [J]. Journal on Communications, 2013, 34(1): 111-120.
[10]	Xiao-mei TIAN,Da-fang ZHANG,Kun XIE,Can HU,Xiao-bo YANG,Chang-qiong SHI. Set reconciliation based on counting Bloom filters [J]. Journal on Communications, 2012, 33(8): 119-127.
[11]	Hai-na TANG,Xiao-la LIN,Chun-jing HAN. Duplicate elimination algorithm for data streams with SKIP Bloom filter [J]. Journal on Communications, 2012, 33(2): 7-14.
[12]	Guo-sheng ZHU,Shao-hua YU. Hish speed deep packet inspection method with low power dissipation [J]. Journal on Communications, 2011, 32(4): 158-165.
[13]	Qiong HUANG,Wen-zhu XIONG,Xiao-long YANG,Jie XU,Ke-ping LONG. Hierarchical stateless single-packet IP traceback technique [J]. Journal on Communications, 2011, 32(3): 150-157.
[14]	Peng HUANG,Yuan-bo GUO,Wei LIU. Design of a hardware-based high-speed multi-pattern matching structure for network security applications [J]. Journal on Communications, 2010, 31(9A): 190-196.
[15]	Tao ZOU,Qing MIAO,Li LIU,Cui ZHANG. Performance analyzing of data reduction in network forensics system for chinese text content [J]. Journal on Communications, 2009, 30(10A): 93-96.