资源描述：
《布鲁姆过滤器查询算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.20,No.1,January2009,pp.96−108http://www.jos.org.cndoi:10.3724/SP.J.1001.2009.03458Tel/Fax:+86-10-62562563©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.∗布鲁姆过滤器查询
2、算法1+123谢鲲,文吉刚,张大方,谢高岗1(湖南大学计算机与通信学院,湖南长沙410082)2(湖南大学软件学院,湖南长沙410082)3(中国科学院计算技术研究所网络与普适计算研究部,北京100190)BloomFilterQueryAlgorithm1+123XIEKun,WENJi-Gang,ZHANGDa-Fang,XIEGao-Gang1(CollegeofComputerandCommunication,Hu’nanUniversity,Changsha410082,China)2(S
3、choolofSoftware,Hu’nanUniversity,Changsha410082,China)3(NetworkingandUbiquitousComputingDepartment,InstituteofComputingTechnology,TheChineseAcademyofSciences,Beijing100190,China)+Correspondingauthor:E-mail:xiekun@hnu.cnXieK,WenJG,ZhangDF,XieGG.Bloomfil
4、terqueryalgorithm.JournalofSoftware,2009,20(1):96−108.http://www.jos.org.cn/1000-9825/3458.htmAbstract:ThispapersurveysthemathematicsbehindBloomfilters,someimportantvariationsandnetwork-relatedapplicationsofBloomfilters.Thecurrentresearchesshowthatalth
5、oughBloomfiltersstartdrawingsignificantattentionfromtheacademiccommunityandtherehasbeenconsiderableprogress,therearestillmanyunknowndimensionstobeexplorered.TheresearchtrendsofBloomfilteralgorithmareforeseenintheend.Keywords:Bloomfilter;computernetwork
6、;distributedcomputing;datasetmembershipquery摘要:从理论和应用两方面系统地综述了布鲁姆过滤器查询算法迄今为止的主要研究成果,分析了目前布鲁姆过滤器查询算法的研究现状,最后展望了布鲁姆过滤器查询算法未来可能的研究方向.关键词:布鲁姆过滤器,计算机网络,分布式计算,集合从属查询中图法分类号:TP393文献标识码:A随着计算技术的飞速发展,数据库、网络和其他应用中的数据集合规模呈几何增长.日益增长的网络信息空间给网络资源存储、管理、定位、交互带来了前所未有的挑战
7、.信息的表示和查找是计算机网络和大多数计算机应用程序的核心,是进行资源查找、定位、访问和交换的关键,是网络和分布式系统资源共享最基本的操作.当数据集合变得越来越大,集合的表示和访问就越来越困难,如何表示海量资源信息,如何快速、高效地在海量信息中查找所需的资源成为国、内外学术界的研究热点.因此,在高速发展的网络和计算机系统环境下,研究简洁的结构表示资源信息,设计与之对应的高效查询算法查找定位资源信息,成为提升网络软件体系结构,进行∗SupportedbytheNationalNaturalScienc
8、eFoundationofChinaunderGrantNos.90718008,90604015(国家自然科学基金)Received2007-09-12;Accepted2008-08-07谢鲲等:布鲁姆过滤器查询算法97高效的大规模数据管理的关键,亦成为多种网络应用得以最终推广的基础.[1]作为一种精简的信息表示方案,布鲁姆过滤器(Bloomfilter)能够满足高速网络发展中高效资源交互和查找需求.布鲁姆过滤器对集合采用一个位串表示,并支持元素的哈希查找.既能表
