全部 标题 作者
关键词 摘要

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

查看量下载量

相关文章

更多...
电子学报  2012 

几何布鲁姆过滤器的设计与分析

DOI: 10.3969/j.issn.0372-2112.2012.09.023, PP. 1852-1857

Keywords: 布鲁姆过滤器,几何布鲁姆过滤器,概要数据结构

Full-Text   Cite this paper   Add to My Lib

Abstract:

针对经典计数型布鲁姆过滤器(NCBF)存储和查询性能较低的缺陷,提出了几何布鲁姆过滤器结构GBF.该结构通过引入"哈希指纹"、布鲁姆过滤器两次分割、基于桶负载存放的方法,实现了集合元素的简洁存储、快速查询.基于"微分方程"和"概率论"的相关知识,对GBF模型进行了理论分析和求解,建立了错误概率和计算复杂度的关系表达式,论证了GBF的几何分布特性.仿真结果表明:与NCBF相比,GBF具有较低错误概率和计算复杂度的同时,也能保持较高的空间利用率.

References

[1]  B Bloom.Space/ time tradeoffs in hash coding with allowable errors [J].Communications of the ACM,1970,13(7):422-426.
[2]  Mullin JK.Optimal semi-joins for distributed database systems [J].IEEE Transaction on Software Engineering,1990,16(5):558-560.
[3]  Byers J W,et al.Informed content delivery across adaptive overlay networks [J].IEEE/ACM Transactions on Networking,2002,12(5):767-780.
[4]  王洪波,程时端,林宇.高速网络超链接主机检测中的流抽样算法研究[J].电子学报,2008,36(4):809-818. WANG Hongbo,CHENG Shiduan,LIN Yu.On flow sampling for identifying super-connection hosts [J].Acta Electronica Sinica,2008,36(4):809-818.(in Chinese).
[5]  Rhea SC,Kubiatowicz J.Probabilistic location and routing. IEEE INFOCOM. California:Berkeley,2002.1248-1257.
[6]  Saar C,Yossi M.Spectral Bloom filters. ACM SIGMOD. San Diego:ACM Press,2003.241-252.
[7]  T G Kurtz.Solutions of ordinary differential equations as limits of pure jump Markov processes [J].Journal of Applied Probability,1970,7(1):49-58.
[8]  M Mitzenmacher,E Upfal.Probability and Computing:Randomized Algorithm and Probabilistic Analysis [M].Cambridge,U K:Cambridge Univ Press,2005.823-829.
[9]  Whitaker A,Wetherall D.Forwarding without loops in Icarus. IEEE Open Architectures and Network Programming Proceedings. Washington:University of Washington,2002.63-75.
[10]  L Fan,P Cao,J Almeida,A Z Broder.Summary cache:a scalable wide-area web cache sharing protocol [J].IEEE/ACM Transactions on Networking,2000,8(3):281-293.
[11]  M Mitzenmacher.Compressed Bloom filters [J].IEEE/ACM Transactions on Networking,2002,10(5):604-612.
[12]  Xie K,Ming YH,Zhang DF,Xie GG,Wen JG.Basket Bloom filters for membership queries [J].Chinese Journal of Computers,2007,30(4):597-607.
[13]  Flavio B,Michael M,Rina P,Sushil S,George V.An improved construction for counting Bloom filters. Annual European Symposium. Zurich:Springer-Verlag,2006.684-695.
[14]  A Broder,M Mitzenmacher.Network applications of Bloom filters:a survey [J].Internet Mathematics,2004,1(4):485-509.
[15]  M Mitzenmacher.The Power of Two Choices in Randomized Load Balancing. Berkeley:University of California,1996.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133