布鲁姆过滤器是一种表示集合的空间高效的有损数据结构,支持快速的数据成员查询,能有效地过滤不属于集合的成员。布鲁姆过滤器被广泛应用于数据库、网络和分布式系统,它在需要共享现有数据信息的分布式应用系统中有巨大的应用潜力。针对布鲁姆过滤器算法和应用的研究已被越来越多的研究团体所重视,涌现出了大量布鲁姆过滤器算法的变种及相关应用的研究论文,而且这种快速发展的势头还将持续下去,必定会出现更多布鲁姆过滤器算法的相关变种及应用研究。通常我们使用布鲁姆过滤器的一般场景是：将集合S表示到布鲁姆过滤器这一精简结构中,在需要查询元素是否属于集合S时,使用布鲁姆过滤器而不是集合S本身进行集合成员查询,节约存储空间及提高查询的时间效率。目前大多数有关布鲁姆过滤器的扩展算法及应用研究主要是针对单个布鲁姆过滤器结构进行的。本文的研究工作则是考察如何使用多个布鲁姆过滤器结构进行相关查询,并将之用于分布式内容分发系统、数据同步系统等。本文对多布鲁姆过滤器查询算法从理论分析和实际应用两个方面进行了深入的研究。首先分析网络高速发展给多布鲁姆过滤器查询算法带来的机遇,指出多布鲁姆过滤器查询算法研究的重要意义。然后,概括了多布鲁姆过滤器查询算法的研究现状和多布鲁姆过滤器查询算法目前的主要研究成果。考虑到单布鲁姆过滤器查询算法在解决分布式数据分发及数据同步等问题时不能完全胜任,本文提出了使用多个布鲁姆过滤器结构进行查询的数个多布鲁姆过滤器查询算法,如双布鲁姆过滤器直接查询算法、计数布鲁姆过滤器代数运算查询算法、使用多个标准布鲁姆过滤器进行查询的数据调和算法及使用多计数布鲁姆过滤器运算的数据调和算法。本文的创新性成果主要体现在以下几个方面：1)探讨双布鲁姆过滤器直接查询法的查询性能探讨直接使用两个集合的布鲁姆过滤器结构查询集合并集、交集、补集、差集或对称差成员的性能问题,即双布鲁姆过滤器直接查询法的性能。理论分析和实验结果表明,双布鲁姆过滤器直接查询法能够较好地支持集合并集、交集、补集、差集及对称差的成员查询问题,其中使用双布鲁姆过滤器直接查询法进行并集查询及交集查询不会产生假阴性,仅有少量假阳性的存在,而双布鲁姆过滤器直接查询法查询补集、差集及对称差则除存在少量假阳性外,还存在少量假阴性,即部分本来属于补集、差集或对称差的元素被判为不属于补集、差集或对称差。2)研究多个计数布鲁姆过滤器向量进行代数运算(简称为计数布鲁姆过滤器代数运算)的性质由于在使用双布鲁姆过滤器直接查询法查询补集、差集及对称差元素时,存在假阴性问题,因此,我们尝试从计数布鲁姆过滤器向量运算的角度寻求能解决前述假阴性问题的方法,探讨两个或多个计数布鲁姆过滤器的代数运算和集合运算的一致性关系,研究使用计数布鲁姆过滤器代数运算进行集合成员查询的性能。理论分析和实验结果表明,计数布鲁姆过滤器的并、交、补、减、异或运算产生的新过滤器依然保持计数布鲁姆过滤器的特征,支持元素的删除操作,不会出现假阴性,能用于集合并集、交集、补集、差集及对称差的成员查询；与双布鲁姆过滤器直接查询法相比,使用计数布鲁姆过滤器代数运算后的过滤器进行补集、差集及对称差成员查询,不存在前述假阴性问题,空间效率能提高一倍,时间效率亦能显著地得到改善。计数布鲁姆过滤器代数运算的使用有利于进一步扩展计数布鲁姆过滤器的应用范围。3)提出基于多标准布鲁姆过滤器运算的精确集合调和方法分布式系统中,集合调和是指分布式节点交换各自节点的数据集合本身或数据集合的某种表示,找出集合的差集元素,进而获得数据集合并集的过程,在这一过程中,节点间花费的通信代价(节点间的消息交换轮数及传输消息位数)越少越好。集合调和问题对于分布式文件分发、闲谈协议、同步与复制协议等分布式计算应用来说,是一个重要的基础构件。本文在分析现有特征多项式插值精确集合调和法的工作原理的基础上,提出了一种基于多标准布鲁姆过滤器运算的精确集合调和方法(BFESR)。使用特征多项式插值调和法(Characteristic polynomial interpolation-based synchronization, CPISync)时有一个前提：插值时的求值点数要大于对称差规模(即|SA-SR|+|SB-SA|)。分布式系统中,对称差规模的上界值往往无法事先获知,从而不能简单地调用CPISync算法完成调和。现有的解决方法通常是使用试探法,即逐次增加求值点数和特征多项式值个数,直至求值点总数超过对称差规模,才能成功插值,实现集合调和。BFESR首先使用两个布鲁姆过滤器的内积运算或本文提出的准交集查询法估算出对称差规模；然后以逐轮增加的求值点和特征多项式值作为插值算法的输入,重复调用插值算法,直至确认成功；最后进行因式分解得到差集元素,进而获取并集完成调和。通常,BFESR调和过程中,调用一次插值算法即能成功。理论分析和实验结果表明,使用布鲁姆过滤器内积运算和准交集查询法估算对称差规模,其准确程度均较高,而且准交集查询法得到的估算值更为接近实际对称差规模。与已有的试探法进行比较,BFESR调和时间和消息交换轮数降低非常明显,尤其是使用准交集查询法估算对称差规模的BFESR方法,其调和效率更高。4)提出基于多计数布鲁姆过滤器运算的精确集合调和方法由于BFESR算法中使用的标准布鲁姆过滤器不支持集合元素的动态更新,若用于更新频繁的P2P网络等分布式系统则需要定时重建标准布鲁姆过滤器,这样会增加系统实现的负担及难度,因此,为解决BFESR调和算法的这一应用局限性,本文提出了一种基于多计数布鲁姆过滤器运算的精确集合调和方法(CBFESR),该方法将集合用计数布鲁姆过滤器表示,利用计数布鲁姆过滤器减运算得到的新过滤器,查询并获得集合中的差集元素,再用差集和自身集合进行集合并运算,完成集合调和。理论分析和在P2P系统中的仿真实验结果表明,CBFESR既具有精确集合调和能得到全部差集元素的优点,也具有近似集合调和仅需单轮消息交换、计算简单的优点。此外,由于计数布鲁姆过滤器支持集合元素的删除操作,因此,CBFESR非常适合应用于数据集合更新频繁的P2P网络等分布式系统。