全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
电子学报  2015 

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

DOI: 10.3969/j.issn.0372-2112.2015.04.005, PP. 652-657

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]  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.
[2]  Andrei B,Michael M.Network applications of Bloom filters:a survey[J].Internet Mathematics,2005,1(4):485-509.
[3]  谢鲲,赵姣姣,张大方,等.基于计数布鲁姆过滤器的快速多维包分类算法[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)
[4]  刘威,郭渊博,黄鹏.基于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)
[5]  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.
[6]  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.
[7]  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.
[8]  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.
[9]  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.
[10]  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.
[11]  肖明忠,代亚非,李晓明.拆分型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)
[12]  张震,汪斌强,陈庶樵,等.几何布鲁姆过滤器的设计与分析[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)
[13]  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.
[14]  谢鲲,秦拯,文吉刚,等.联合多维布鲁姆过滤器查询算法[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)
[15]  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.
[16]  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.
[17]  左孝凌,刘永才.离散数学[M].上海:上海科学技术文献出版社,1982.166-168. Zuo Xiaoling,Liu Yongcai.Discrete Mathematics[M].Shanghai:Shanghai Scientific & Technological Literature Publishing House,1982.166-168.( in Chinese)

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133