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

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

通信学报 ›› 2016, Vol. 37 ›› Issue (3): 139-147.doi: 10.11959/j.issn.1000-436x.2016061

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

王勇¹,云晓春^1,²,王树鹏¹,王曦¹

¹ 中国科学院信息工程研究所北京100093
² 国家计算机网络应急技术处理协调中心北京100029

出版日期:2016-03-25 发布日期:2017-08-04
基金资助:
国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家自然科学基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目;国家高技术研究发展计划(“863”计划)基金资助项目

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

Yong WANG¹,Xiao-chun YUN^1,²,ANGShu-peng WANG¹,Xi WANG¹

¹ Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China
² National Computer Network Emergency Response Technical Team/Coordination Center of China,Beijing 100029,China

Online:2016-03-25 Published:2017-08-04
Supported by:
The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National Natural Science Foundation of China;The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program);The National High Technology Research and Development Program of China (863 Program)

摘要/Abstract

摘要：

为了提升多维元素成员查询的灵活性和准确率，提出了一种新型索引结构CBFM(cutted Bloom filter matrix)。该索引方法通过独立属性布鲁姆过滤器笛卡尔乘积构建位矩阵，支持任意属性组合的多维元素成员查询，同时支持属性组合按需删减和属性加权，极大地提升内存空间利用率，降低查询误判率。理论分析证明相比于BFM(Bloom filter matrix)索引方法，CBFM具有更高的内存利用率。仿真实验表明，在分配内存相同的情况下，CBFM方法相比于其他方法，具有最低的查询误判率，特别在内存受限场景下，CBFM相比于BFM方法，查询误判率最大降低3个数量级，极大地提升了多维元素成员查询的准确率。

关键词: 查询算法, 多维元素成员查询, 布鲁姆过滤器, 位矩阵

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

王勇,云晓春,王树鹏,王曦. CBFM：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法[J]. 通信学报, 2016, 37(3): 139-147.

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.

图/表 15

图1

表1

CBFM运行参数"

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

表1

图2

图3

图4

图5

图6

表2

表3

图7

图8

图9

图10

图11

图12

参考文献 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.

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：支持属性删减的布鲁姆过滤器矩阵多维元素查询算法

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 19

相关文章 7

Metrics

推荐阅读 0

[1]	梁茹冰,刘琼. 断接下移动终端的简单查询算法研究[J]. 通信学报, 2014, 35(3): 201-207.
[2]	梁茹冰1，刘琼2. 断接下移动终端的简单查询算法研究[J]. 通信学报, 2014, 35(3): 23-207.
[3]	侯颖，郭云飞，黄海，王凯. 基于同源组合布鲁姆过滤器的早期流量抽样算法[J]. 通信学报, 2014, 35(10): 14-126.
[4]	侯颖,郭云飞,黄海,王凯. 基于同源组合布鲁姆过滤器的早期流量抽样算法[J]. 通信学报, 2014, 35(10): 117-126.
[5]	田小梅,张大方,谢鲲,胡灿,杨晓波,史长琼. 基于计数布鲁姆过滤器的集合调和算法[J]. 通信学报, 2012, 33(8): 119-127.
[6]	朱国胜,余少华. 高速低功耗深度报文检测方法[J]. 通信学报, 2011, 32(4): 158-165.
[7]	谢鲲,秦拯,文吉刚,张大方,谢高岗. 联合多维布鲁姆过滤器查询算法[J]. 通信学报, 2008, 29(1): 56-64.