面向大数据处理的高精度多维计数布鲁姆过滤器

doi:10.3969/j.issn.0372-2112.2015.04.005

电子学报 ›› 2015, Vol. 43 ›› Issue (4): 652-657.DOI: 10.3969/j.issn.0372-2112.2015.04.005

面向大数据处理的高精度多维计数布鲁姆过滤器

李玮¹, 张大方¹, 黄昆², 谢鲲¹

1. 湖南大学信息科学与工程学院, 湖南长沙 410082;
2. 中国科学院计算技术研究所, 北京 100190

收稿日期:2013-01-05 修回日期:2014-07-28 出版日期:2015-04-25
- 作者简介:
- 李玮男,1972年生,助理教授,博士生,研究方向大数据处理、软件工程、可信系统与网络.E-mail:rj_wli@hnu.edu.cn;张大方 男,1959年生,教授、博导,博士,研究方向可信系统与网络、软件工程、大数据处理.E-mail:dfzhang@hnu.edu.cn;黄昆男,1978年生,助理研究员,博士,研究方向可信系统与网络、大数据处理.E-mail:huangkun09@ict.ac.cn;谢鲲女,1978年生,副教授,博士,研究方向为分布式计算、协作路由、大数据处理.E-mail:xiekun@hnu.edu.cn
- 基金资助:
- 国家重点基础研究发展规划 (973计划) (No.2012CB315805); 国家自然科学基金 (No.61173167); 江苏省未来网络前瞻性研究项目 (No.BY2013095-1-05); 湖南省科技计划 (No.2013SK3149)

Accurate Multi-Dimension Counting Bloom Filter for Big Data Processing

LI Wei¹, ZHANG Da-fang¹, HUANG Kun², XIE Kun¹

1. College of Computer Science and Electronics Engineering, Hunan University, Changsha, Hunan 410082, China;
2. Institute of Computing Technology, CAS, Beijing 100190, China

Received:2013-01-05 Revised:2014-07-28 Online:2015-04-25 Published:2015-04-25

摘要/Abstract

摘要：

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法.AMD-CBF中元素表示和查找分两步进行,第1步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第2步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息,然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF),完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,AMD-CBF能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高.

关键词: 大数据处理, 多维布鲁姆过滤器, 双射函数, 高精度计数布鲁姆过滤器, 假阳性

Abstract:

Based on the analysis of multi-dimension Bloom filter presented before,an accurate multi-dimension counting Bloom filter(AMD-CBF) query algorithm based on bijective function is proposed for big data processing.When representing or querying an element,AMD-CBF needs two steps.The first step is to hash and map each attribute of the element to their corresponding accurate counting Bloom filter (A-CBF);The second step is to transform all attributes of the element into a value by bijective function to represent the overall information of the element,then the value is hashed and mapped into a combined counting Bloom filter (C-CBF)for completing the representation and query confirmation of the elements overall.Both theoretical analysis and experiment show that the AMD-CBF can support concise representation,approximate membership query and deletion of multi-dimension data set and significantly lower false positive rate and improve query accuracy compared to similar research.

Key words: big data processing, multi-dimension Bloom filter, bijective function, accurate counting Bloom filter, false positive

中图分类号:

TP393

李玮, 张大方, 黄昆, 谢鲲. 面向大数据处理的高精度多维计数布鲁姆过滤器[J]. 电子学报, 2015, 43(4): 652-657.

LI Wei, ZHANG Da-fang, HUANG Kun, XIE Kun. Accurate Multi-Dimension Counting Bloom Filter for Big Data Processing[J]. Acta Electronica Sinica, 2015, 43(4): 652-657.

参考文献

[1] Andrei B,Michael M.Network applications of Bloom filters:a survey[J].Internet Mathematics,2005,1(4):485-509.
[2] 谢鲲,赵姣姣,张大方,等.基于计数布鲁姆过滤器的快速多维包分类算法[J].电子学报,2010,38(5):1046-1052. Xie Kun,Zhao Jiaojiao,Zhang Dafang,et al.A fast multi-dimensional packet classification algorithm using counting Bloom filter[J].Acta Electronica Sinica,2010,38(5):1046-1052.(in Chinese)
[3] 刘威,郭渊博,黄鹏.基于Bloom filter的多模式匹配引擎[J].电子学报,2010,38(5):1095-1099. Liu Wei,Guo Yuanbo,Huang Peng.Multi-pattern matching engine based on Bloom filter[J].Acta Electronica Sinica,2010,38(5):1095-1099.(in Chinese)
[4] Heeyeol Yu,Rabi N.A power and throughput-efficient packet classification with n Bloom filters[J].IEEE Trans on Computers,2011,60(8):1182-1193.
[5] Siyuan Liu,Lei Kang,Lei Chen,et al.Distributed incomplete pattern matching via a novel weighted Bloom filter[A].Proc of the 32nd International Conference on Distributed Computing Systems[C]. Piscataway,NJ:IEEE,2012.122-131.
[6] Jiansheng Wei,Ke Zhou.Efficiently representing membership for variable large data sets[J].IEEE Trans on Parallel and Distributed Systems,2014,25(4):960-970.
[7] Yan Qiao,Tao Li,Shigang Chen.Fast Bloom filters and their generalization[J].IEEE Trans on Parallel and Distributed Systems,2014,25(1):93-103.
[8] Fan Li,Cao Pei,Almeida J,et al.Summary cache:a scalable wide-area web cache sharing protocol[J].IEEE Trans on Networking,2000,8(3):281-293.
[9] Saar Cohen,Yossi Matias.Spectral Bloom filters[A].Proc of ACM SIGMOD International Conference on Management of Data[C].New York:ACM,2003.241-252.
[10] 肖明忠,代亚非,李晓明.拆分型Bloom Filter[J].电子学报,2004,32(2):241-245. Xiao Mingzhong,Dai Yafei,Li Xiaoming.Split Bloom filter[J].Acta Electronica Sinica,2004,32(2):241-245.(in Chinese)
[11] 张震,汪斌强,陈庶樵,等.几何布鲁姆过滤器的设计与分析[J].电子学报,2012,40(9):1852-1857. Zhang Zhen,Wang Binqiang,Chen Shuqiao,et al.Geometric Bloom filter designing and its analysis[J].Acta Electronica Sinica,2012,40(9):1852-1857.(in Chinese)
[12] Deke Guo,Jie Wu,Honghui Chen,et al.Theory and network application of dynamic Bloom filters[A].Proc of the 25th Annual International Conference on Computer Communications[C].Piscataway,NJ:IEEE,2006.1-12.
[13] 谢鲲,秦拯,文吉刚,等.联合多维布鲁姆过滤器查询算法[J].通信学报,2008,29(1):56-64. Xie Kun,Qin Zheng,Wen Jigang,et al.Combine multi-dimension Bloom filter for membership queries[J].Journal on Communications,2008,29(1):56-64.(in Chinese)
[14] Bin Xiao,Yu Hua.Using parallel Bloom filters for multi-attribute representation on network services[J].IEEE Trans on Parallel and Distributed Systems,2010,21(1):20-32.
[15] Domenico Ficara,Stefano Giordano,Gregorio Procissi,et al.Multilayer compressed counting Bloom filters[A].Proc of the 27th Annual International Conference on Computer Communications[C].Piscataway,NJ:IEEE,2008.932-941.
[16] 左孝凌,刘永才.离散数学[M].上海:上海科学技术文献出版社,1982.166-168. Zuo Xiaoling,Liu Yongcai.Discrete Mathematics[M].Shanghai:Shanghai Scientific & Technological Literature Publishing House,1982.166-168.( in Chinese)
[17] NLANR.Index of /datasets/wits.cs.waikato.ac.nz/pma/Traces[EB /OL].https://labs.ripe.net/datarepository/data-sets/nlanr-pma-data,2005-07-01.

面向大数据处理的高精度多维计数布鲁姆过滤器

Accurate Multi-Dimension Counting Bloom Filter for Big Data Processing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	皮德常, 吴致远, 曹建军. 基于知识图谱表示学习的谣言早期检测方法[J]. 电子学报, 2023, (): 1-11.
[2]	金明, 丁蓉. 一种联合时域和空域残差的网络异常检测与节点定位方法[J]. 电子学报, 2022, (): 1-8.
[3]	胡钢, 牛琼, 许丽鹏, 卢志宇, 过秀成. 基于网络超链接信息熵的节点重要性序结构演化建模分析[J]. 电子学报, 2022, 50(11): 2638-2644.
[4]	杨宏宇, 王泽霖, 张良, 成翔. 面向物联网的多协议僵尸网络检测方法[J]. 电子学报, 2022, (): 1-9.
[5]	孟超, 周倩, 郭林, 王攀, 孙知信. 基于相关性传输模型的无线链路质量估计方法及路由优化算法[J]. 电子学报, 2022, 50(10): 2409-2424.
[6]	蒋伟进, 张婉清, 陈萍萍, 陈君鹏, 孙永霞, 刘权. 基于IWOA群智感知中数量敏感的任务分配方法[J]. 电子学报, 2022, 50(10): 2489-2502.
[7]	杨明亮, 吴春明, 沈丛麒, 邱于兵. 基于IEEE 802.1的TSN交换机队列调度技术研究[J]. 电子学报, 2022, 50(9): 2090-2095.
[8]	熊小峰, 黄淳岚, 乐光学, 戴亚盛, 杨晓慧, 杨忠明. 边缘计算中基于综合信任评价的任务卸载策略[J]. 电子学报, 2022, 50(9): 2134-2145.
[9]	魏振春, 傅宇, 马仲军, 吕增威, 石雷, 张本宏. 带时间窗的无线可充电传感器网络多目标路径规划算法[J]. 电子学报, 2022, 50(8): 1819-1829.
[10]	赵耿, 马英杰, 陈磊, 董有恒, 侯艳丽. 基于扰动时空混沌系统的动态S盒设计[J]. 电子学报, 2022, 50(8): 2037-2042.
[11]	欧阳与点, 谢鲲, 谢高岗, 文吉刚. 面向大规模网络测量的数据恢复算法：基于关联学习的张量填充[J]. 电子学报, 2022, 50(7): 1653-1663.
[12]	陈嘉兴, 程杰, 董云玲, 刘志华. 基于弯曲声线和测距修正的水下节点定位算法[J]. 电子学报, 2022, 50(7): 1567-1572.
[13]	易令, 李泽平. 基于深度强化学习的码率自适应算法研究[J]. 电子学报, 2022, 50(5): 1192-1200.
[14]	王志晓, 张磊, 孙成成, 芮晓彬, 黄珍珍, 张孙贤. 基于社区划分与连边逆序放回的网络分解算法[J]. 电子学报, 2022, 50(3): 540-547.
[15]	周奕涛, 张斌, 刘自豪. 基于多模态深度神经网络的应用层DDoS攻击检测模型[J]. 电子学报, 2022, 50(2): 508-512.