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

• 学术论文 • 上一篇    下一篇

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

李玮1, 张大方1, 黄昆2, 谢鲲1   

  1. 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 Wei1, ZHANG Da-fang1, HUANG Kun2, XIE Kun1   

  1. 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

摘要:

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(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

中图分类号: