多布鲁姆过滤器查询算法及其应用研究
|
摘要
布鲁姆过滤器是一种表示集合的空间高效的有损数据结构,支持快速的数据成员查询,能有效地过滤不属于集合的成员。布鲁姆过滤器被广泛应用于数据库、网络和分布式系统,它在需要共享现有数据信息的分布式应用系统中有巨大的应用潜力。针对布鲁姆过滤器算法和应用的研究已被越来越多的研究团体所重视,涌现出了大量布鲁姆过滤器算法的变种及相关应用的研究论文,而且这种快速发展的势头还将持续下去,必定会出现更多布鲁姆过滤器算法的相关变种及应用研究。
通常我们使用布鲁姆过滤器的一般场景是：将集合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网络等分布式系统。
A Bloom filter is an excellent data structure that can succinctly represent a data set in order to support membership queries, and effectively filter out the elements that do not belong to the set. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. Many research communities have been taking deep researches into Bloom filter algorithms and their applications, and there will be more Bloom filter algorithms and their applications to be found.
Usually we use Bloom filter in such a general scene:set5represented in Bloom filter BF(S), when we query whether an element x belong to S, in order to save memory space and to improve query time efficiency, we query BF(S) instead of S1to check whether x belong to S or not. At present most of the variants of Bloom filter algorithm and their applied researches have been conducted on single Bloom filter. The goal of this thesis was to study how to use multi-Bloom-filter query algorithm in P2P systems for content distribution or data synchronization applications.
We conducted in-depth study for multi-Bloom-filter query algorithm in theoretical analysis and practical application. At first we analyzed the opportunities brought about to multi-Bloom-filter query algorithms by the rapid development of the network, and found out that the multi-Bloom-filter query algorithms were worth studying. Secondly we summarized the research status of the multi-Bloom-filter query algorithm and main findings of the multi-Bloom-filter query algorithm. Because single-Bloom-filter query algorithms can not be be fully qualified for solving distributed content distribution and data synchronization problems, we presented a few query algorithms using multiple Bloom filters, such as double-separate-Bloom-filter query algorithm, counting-Bloom-filter algebra operation query algorithm, counting-Bloom-filter based set reconciliation algorithm which use counting-Bloom-filter subtraction operation and Bloom-filter based exact set reconciliation algorithm which use multiple Bloom filters to reconcile sets. Some creative works in this thesis are focused on the following aspects:
1) This thesis examined the problem of membership queries for sets'union, intersection, complementary set, sets'difference or symmetric differences between sets by using double separate Bloom filters. The theoretical analysis and experimental results show that the double-separate-Bloom-filter query algorithm can support membership queries for sets'union, intersection, complementary set, sets'difference or symmetric differences between sets, of which membership queries for sets'union or intersection have no false negatives, only a few false positives, while membership queries for complementary set, sets'difference or symmetric differences between sets have a small number of false negatives in addition to small amounts of false positives.
2) Because membership queries for complementary set, sets'difference or symmetric differences between sets using double separate Bloom filters have a small number of false negatives, we attempted to seek solutions to this problem using algebra operations on counting Bloom filters. This thesis examined the consistence between algebra operations on counting Bloom filters and algebra operations on data sets, and studied the membership query performances of algebra operations on counting Bloom filters. Theoretical analyses and simulations show that the counting Bloom filter which is ORed(ANDed, COMPLEMENTed, SUBTRACTed, XORed) from the original counting Bloom filters can support membership query on the set ORed(ANDed, COMPLEMENTed, SUBTRACTed, XORed) from the original data sets. When using double-separate-counting-Bloom-filter query algorithm to query elements belonged to complementary set, sets'difference or symmetric differences of the two sets, some elements in complementary set, differences or symmetric differences of the sets will be misjudged, while the query method using algebra operations on counting Bloom filters has no false negatives and gain a remarkable improvement in space complexity and time complexity over the method using double-separate-counting-Bloom-filter query method, hence it can be applied to various network fields. For example, counting-Bloom-filter SUB operation can be used in set reconciliation protocol for distributed database or file systems.
3) Set reconciliation aims at efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. Set reconciliation is a fundamental problem in distributed computing, arising in protocols for content delivery, gossiping, synchronization and replication. On the basis of analyzing the existing accurate set reconciliation algorithm using characteristic polynomial interpolation-based synchronization (CPISync), we presented an exact set reconciliation algorithm based on multiple Bloom filters (BFESR). There is a premise when we use CPISync to reconcile data:the number of evaluated points shoud be greater than the size of the symmetric differences between remote sets (|SA-SB|+|SB-SA|). In distributed systems, the size of the symmetric differences between remote sets is often unable to be known in advance, therefore CPISync algorithm can not be simply invoked to reconcile data. Existing solutions to this problem are usually heuristics that iteratively increase the number of evaluated points and characteristic polynomial values until the total number of evaluated points exceeds the size of the symmetric differences, then successful interpolation is achieved. These heuristics have too long reconciliation latency. BFESR has less reconciliation latency. The basic idea of BFESR is to obtain symmetric difference size between remote sets before calling CPISync algorithm, thus characteristic polynomial values for CPISync algorithm are wholesale transferred. At first, BFESR estimates symmetric difference size between remote sets SA and SB using Bloom filters, and calculates the same number of characteristic polynomial values as the estimated size of the symmetric differences between SA and SB, and then interpolates rational polynomials, finally recovers the sets SA-SB and SB-SA through factoring the rational polynomials and gets the union of SA and SB-Theoretical analyses and experimental results show that, compared with the existing methods for exact set reconciliation, BFESR needs only a single round-trip to get the accurate union of the sets in most cases, thus greatly reducing reconciliation latency. BFESR uses Bloom filters'inner-product or quasi-intersection query method to estimate the size of the symmetric difference between sets, both methods have higher estimating accuracy, and the quasi-intersection query method estimates closer to the actual size of the symmetric differences between sets. Compared with existing heuristics for exact set reconciliation, BFESR has very significantly less reconciliation time and fewer message exchange rounds, particularly when BFESR uses quasi-intersection query method to estimate the size of the symmetric differences between sets.
4) Because Bloom filters used in BFESR does not support dynamic update of set elements, BFESR is not suitable for data reconciliation in update-intensive distributed systems. To solve this application limitation of BFESR algorithm, we present a new set reconciliation algorithm based on multiple counting Bloom filters, which we call Counting-Bloom-filter based exact set reconciliation(CBFESR). This method represents sets SA and SB as counting Bloom filters, subtracts SA's counting Bloom filter from SB'S counting Bloom filter, the differences we denote CBF(SB)-CBF(SA), then determines SB-SA elements in SB with CBF(SB)-CBF(SA), and finally performs union operation on SB-SA and SA. Counting-Bloom-filter based set reconciliation combines the advantages of exact set reconciliation and approximate set reconciliation, besides gaining all SB-SA elements with single-round messgage exchange, it can also be applied to update-intensive distributed systems because counting Bloom filters support element deletion operation.
通常我们使用布鲁姆过滤器的一般场景是：将集合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网络等分布式系统。
A Bloom filter is an excellent data structure that can succinctly represent a data set in order to support membership queries, and effectively filter out the elements that do not belong to the set. It is widely used in databases, networks and distributed systems and it has great potential for distributed applications where systems need to share information about available data. Many research communities have been taking deep researches into Bloom filter algorithms and their applications, and there will be more Bloom filter algorithms and their applications to be found.
Usually we use Bloom filter in such a general scene:set5represented in Bloom filter BF(S), when we query whether an element x belong to S, in order to save memory space and to improve query time efficiency, we query BF(S) instead of S1to check whether x belong to S or not. At present most of the variants of Bloom filter algorithm and their applied researches have been conducted on single Bloom filter. The goal of this thesis was to study how to use multi-Bloom-filter query algorithm in P2P systems for content distribution or data synchronization applications.
We conducted in-depth study for multi-Bloom-filter query algorithm in theoretical analysis and practical application. At first we analyzed the opportunities brought about to multi-Bloom-filter query algorithms by the rapid development of the network, and found out that the multi-Bloom-filter query algorithms were worth studying. Secondly we summarized the research status of the multi-Bloom-filter query algorithm and main findings of the multi-Bloom-filter query algorithm. Because single-Bloom-filter query algorithms can not be be fully qualified for solving distributed content distribution and data synchronization problems, we presented a few query algorithms using multiple Bloom filters, such as double-separate-Bloom-filter query algorithm, counting-Bloom-filter algebra operation query algorithm, counting-Bloom-filter based set reconciliation algorithm which use counting-Bloom-filter subtraction operation and Bloom-filter based exact set reconciliation algorithm which use multiple Bloom filters to reconcile sets. Some creative works in this thesis are focused on the following aspects:
1) This thesis examined the problem of membership queries for sets'union, intersection, complementary set, sets'difference or symmetric differences between sets by using double separate Bloom filters. The theoretical analysis and experimental results show that the double-separate-Bloom-filter query algorithm can support membership queries for sets'union, intersection, complementary set, sets'difference or symmetric differences between sets, of which membership queries for sets'union or intersection have no false negatives, only a few false positives, while membership queries for complementary set, sets'difference or symmetric differences between sets have a small number of false negatives in addition to small amounts of false positives.
2) Because membership queries for complementary set, sets'difference or symmetric differences between sets using double separate Bloom filters have a small number of false negatives, we attempted to seek solutions to this problem using algebra operations on counting Bloom filters. This thesis examined the consistence between algebra operations on counting Bloom filters and algebra operations on data sets, and studied the membership query performances of algebra operations on counting Bloom filters. Theoretical analyses and simulations show that the counting Bloom filter which is ORed(ANDed, COMPLEMENTed, SUBTRACTed, XORed) from the original counting Bloom filters can support membership query on the set ORed(ANDed, COMPLEMENTed, SUBTRACTed, XORed) from the original data sets. When using double-separate-counting-Bloom-filter query algorithm to query elements belonged to complementary set, sets'difference or symmetric differences of the two sets, some elements in complementary set, differences or symmetric differences of the sets will be misjudged, while the query method using algebra operations on counting Bloom filters has no false negatives and gain a remarkable improvement in space complexity and time complexity over the method using double-separate-counting-Bloom-filter query method, hence it can be applied to various network fields. For example, counting-Bloom-filter SUB operation can be used in set reconciliation protocol for distributed database or file systems.
3) Set reconciliation aims at efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. Set reconciliation is a fundamental problem in distributed computing, arising in protocols for content delivery, gossiping, synchronization and replication. On the basis of analyzing the existing accurate set reconciliation algorithm using characteristic polynomial interpolation-based synchronization (CPISync), we presented an exact set reconciliation algorithm based on multiple Bloom filters (BFESR). There is a premise when we use CPISync to reconcile data:the number of evaluated points shoud be greater than the size of the symmetric differences between remote sets (|SA-SB|+|SB-SA|). In distributed systems, the size of the symmetric differences between remote sets is often unable to be known in advance, therefore CPISync algorithm can not be simply invoked to reconcile data. Existing solutions to this problem are usually heuristics that iteratively increase the number of evaluated points and characteristic polynomial values until the total number of evaluated points exceeds the size of the symmetric differences, then successful interpolation is achieved. These heuristics have too long reconciliation latency. BFESR has less reconciliation latency. The basic idea of BFESR is to obtain symmetric difference size between remote sets before calling CPISync algorithm, thus characteristic polynomial values for CPISync algorithm are wholesale transferred. At first, BFESR estimates symmetric difference size between remote sets SA and SB using Bloom filters, and calculates the same number of characteristic polynomial values as the estimated size of the symmetric differences between SA and SB, and then interpolates rational polynomials, finally recovers the sets SA-SB and SB-SA through factoring the rational polynomials and gets the union of SA and SB-Theoretical analyses and experimental results show that, compared with the existing methods for exact set reconciliation, BFESR needs only a single round-trip to get the accurate union of the sets in most cases, thus greatly reducing reconciliation latency. BFESR uses Bloom filters'inner-product or quasi-intersection query method to estimate the size of the symmetric difference between sets, both methods have higher estimating accuracy, and the quasi-intersection query method estimates closer to the actual size of the symmetric differences between sets. Compared with existing heuristics for exact set reconciliation, BFESR has very significantly less reconciliation time and fewer message exchange rounds, particularly when BFESR uses quasi-intersection query method to estimate the size of the symmetric differences between sets.
4) Because Bloom filters used in BFESR does not support dynamic update of set elements, BFESR is not suitable for data reconciliation in update-intensive distributed systems. To solve this application limitation of BFESR algorithm, we present a new set reconciliation algorithm based on multiple counting Bloom filters, which we call Counting-Bloom-filter based exact set reconciliation(CBFESR). This method represents sets SA and SB as counting Bloom filters, subtracts SA's counting Bloom filter from SB'S counting Bloom filter, the differences we denote CBF(SB)-CBF(SA), then determines SB-SA elements in SB with CBF(SB)-CBF(SA), and finally performs union operation on SB-SA and SA. Counting-Bloom-filter based set reconciliation combines the advantages of exact set reconciliation and approximate set reconciliation, besides gaining all SB-SA elements with single-round messgage exchange, it can also be applied to update-intensive distributed systems because counting Bloom filters support element deletion operation.
引文
[1]马华东,刘亮,李建中.物联网研究进展.见：中国计算机科学技术发展报告2010.北京：机械工业出版社,2011,102-112
[2]徐恪等.新一代互联网体系结构可演进性研究进展.见：中国计算机科学技术发展报告2010.北京：机械工业出版社,2011,72-101
[3]任丰原,林闯.无线传感器网络的现状与发展.见：中国计算机科学技术发展报告2005.北京：清华大学出版社,2006,110-127
[4]张为民等.云计算深刻改变未来.北京：科学出版社,2009
[5]冯丹等.海量存储系统及技术研究进展.见：中国计算机科学技术发展报告2010.北京：机械工业出版社,2011,46-71
[6]中国互联网络信息中心.第30次中国互联网络发展状况统计报告,http://www. cnnic.org.cn/hlwfzyj/hlwxzbg/hlwtjbg/201207/t20120723_32497.htm,2012.7.19
[7]大数据时代降临.http://today.banyuetan.org/jrt/120922/70953.shtml
[8]Bloom B H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM,1970,13(7):422-426
[9]Tarkoma S, Rothenberg C, Lagerspetz E. Theory and practice of bloom filters for distributed systems. IEEE Communications Surveys & Tutorials,2012,14(1):131-155
[10]Jerzak Z, Fetzer C. Bloom filter based routing for content-based publish/subscribe. In: Proceedings of the Second International Conference on Distributed Event-based Systems,2008,71-81
[11]Byers J, Considine J, Mitzenmacher M, et al. Informed content delivery across adaptive overlay networks. ACM SIGCOMM Computer Communication Review,2002,32(4): 47-60
[12]Abdel-Ghaffar K A S, El Abbadi A. An optimal strategy for comparing file copies. IEEE Transactions on Parallel and Distributed Systems,1994,5(1):87-93
[13]Starobinski D, Trachtenberg A, Agarwal S. Efficient PDA synchronization. IEEE Transactions on Mobile Computing,2003,2(1):40-51
[14]Reynolds P, Vahdat A. Efficient peer-to-peer keyword searching. In:Proceedings of the middleware 2003, Lecture Notes in Computer Science,2003,21-40
[15]Czerwinski S E, Zhao B Y, Hodes T D, et al. An architecture for a secure service discovery service. In:Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking,1999,24-35
[16]Rhea S, Kubiatowicz J. Probabilistic location and routing. In:Proceedings of the INFOCOM 2002,2002,1248-1257
[17]Mullin J K, Margoliash D J. A tale of three spelling checkers. Software:Practice and Experience,1990,20(6):625-630
[18]McIlroy M. Development of a spelling list. IEEE Transactions on Communications, 1982,30(1):91-99
[19]Spafford E H. Opus:Preventing weak password choices. Computers & Security,1992, 11(3):273-278
[20]Manber U, Wu S. An algorithm for approximate membership checking with application to password security. Information Processing Letters,1994,50(4):191-197
[21]Bratbergsengen K. Hashing Hethods And Relational Algebra Operations. In: Proceedings of the tenth International Conference on Very Large Databases,1984, 323-333
[22]Valduriez P, Gardarin G. Join and semijoin algorithms for a multiprocessor database machine. ACM Transactions on Database Systems (TODS),1984,9(1):133-161
[23]Mackert L F. R* optimizer validation and performance evaluation for distributed queries. In:Proceedings of the Twelfth International Conference on Very Large Databases,1988,149-159
[24]Mullin J K. Optimal semijoins for distributed database systems. IEEE Transactions on Software Engineering,1990,16(5):558-560
[25]Mullin J K. Estimating the size of a relational join. Information Systems,1993,18(3): 189-196
[26]Gremillion L L. Designing a Bloom filter for differential file access. Communications of the ACM,1982,25(9):600-604
[27]Mullin J K. A second look at Bloom filters. Communications of the ACM,1983,26(8): 570-571
[28]Kim Y, Cho K, Yoon J, et al. Using Bloom Filters for Mining Top-k Frequent Itemsets in Data Streams. Secure and Trust Computing, Data Management and Applications. J. J. Park, J. Lopez, S.-S. Yeo, T. Shon and D. Taniar, Springer Berlin Heidelberg.2011,186: 209-216
[29]Aditya T, Baruah P, Mukkamala R. Employing Bloom Filters for Enforcing Integrity of Outsourced Databases in Cloud Environments. Advances in Computing and Communications,2011:446-460
[30]谢鲲,文吉刚,张大方等.布鲁姆过滤器查询算法.软件学报,2009,20(1)：96-108
[31]Broder A, Mitzenmacher M. Network applications of bloom filters:A survey. Internet Mathematics,2005,1(4):485-509
[32]Song H, Dharmapurikar S, Turner J, et al. Fast hash table lookup using extended bloom filter:an aid to network processing. In:Proceedings of the SIGCOMM'05,2005, 181-192
[33]Song H, Hao F, Kodialam M, et al. Ipv6 lookups using distributed and load balanced bloom filters for 100gbps core router line cards. In:Proceedings of the INFOCOM 2009,2009,2518-2526
[34]Dharmapurikar S, Krishnamurthy P, Sproull T, et al. Deep packet inspection using parallel bloom filters. In:Proceedings of the 11th Symposium on High Performance Interconnects,2003,44-51
[35]Chen Y, Oguntoyinbo O. Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks. Computer Communications, 2009,32(2):349-356
[36]Dharmapurikar S, Song H, Turner J, et al. Fast packet classification using bloom filters. In:Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems,2006,61-70
[37]Ahmadi M, Wong S. Modified collision packet classification using counting bloom filter in tuple space. In:Proceedings of the 25th IASTED Conference on Parallel and Distributed Computing and Networks,2007,315-320
[38]谢鲲,赵姣姣,张大方等.基于计数布鲁姆过滤器的快速多维包分类算法.电子学报,2010,38(5)：1046-1052
[39]Estan C, Varghese G. New directions in traffic measurement and accounting. In: Proceedings of the ACM SIGCOMM 2002,2002,323-336
[40]Feng W, Shin K G, Kandlur D D, et al. The BLUE active queue management algorithms. IEEE/ACM Transactions on Networking (TON),2002,10(4):513-528
[41]吴桦,龚俭,杨望.一种基于双重Counter Bloom Filter的长流识别算法.软件学报,2010,21(5)：1115-1126
[42]Zhao Q G, Ogihara M, Wang H, et al. Finding global icebergs over distributed data sets. In:Proceedings of the Twentyfifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,2006,298-307
[43]Laufer R P, Velloso P B, de O Cunha D, et al. Towards stateless single-packet IP traceback. In:Proceedings of the 32nd IEEE Conference on Local Computer Networks, 2007,548-555
[44]Snoeren A C, Partridge C, Sanchez L A, et al. Single-packet IP traceback. IEEE/ACM Transactions on Networking (TON),2002,10(6):721-734
[45]Snoeren A C, Partridge C, Sanchez L A, et al. Hash-based IP traceback. In:Proceedings of the 2001 SIGCOMM Conference,2001,3-14
[46]Pang M, Xu G. A personalized search engine research based on Bloom filter. In: Proceedings of the 2011 International Conference on Electric Engineering and Computer (MEC),2011,2365-2368
[47]He W, Lv T. Bloom filter-based keyword search over XML data in structured Peer-to-Peer systems. In:Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology,2010,177-181
[48]Kumar A, Xu J, Zegura E W. Efficient and scalable query routing for unstructured peer-to-peer networks. In:Proceedings of the INFOCOM 2005,2005,1162-1173
[49]Minsky Y, Trachtenberg A. Efficient reconciliation of unordered databases, Cornell University,1999
[50]Eppstein D, Goodrich M T, Uyeda F, et al. What's the difference?Efficient set reconciliation without prior context. In:Proceedings of the ACM SIGCOMM 2011, 2011,218-229
[51]Skjegstad M, Maseng T. Low complexity set reconciliation using Bloom filters. In: Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing,2011,33-41
[52]Zhao T, Liu Z, Yan W, et al. BFBD:A Bloom Filter based Buffering Data Dissemination algorithm for Vehicular Ad hoc Networks. In:Proceedings of the 2011 IEEE Consumer Communications and Networking Conference (CCNC),2011, 447-481
[53]Melsted P, Pritchard J K. Efficient counting of k-mers in DNA sequences using a bloom filter. BMC bioinformatics,2011,12(1):1-7
[54]Ma L, Chamberlain R D, Buhler J D, et al. Bloom Filter Performance on Graphics Engines. In:Proceedings of the 2011 International Conference on Parallel Processing, 2011,522-531
[55]肖军,云晓春,张永铮.随机伪造源地址分布式拒绝服务攻击过滤.软件学报,2011,22(10)：2425-2437
[56]Bellovin S M, Cheswick W R. Privacy-enhanced searches using encrypted bloom filters, Columbia University and AT&T,2004
[57]Antichi G, Ficara D, Giordano S, et al. Counting bloom filters for pattern matching and anti-evasion at the wire speed. IEEE Network,2009,23(1):30-35
[58]Ballani H, Chawathe Y, Ratnasamy S, et al. Off by default! In:Proceedings of the 4th ACM Workshop on Hot Topics in Networks (Hotnets-IV),2005
[59]Wang X F, Reiter M K. Mitigating bandwidth-exhaustion attacks using congestion puzzles. In:Proceedings of the 11th ACM Conference on Computer and Communications Security,2004,257-267
[60]Ye F, Luo H, Lu S, et al. Statistical en-route filtering of injected false data in sensor networks. In:Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2004,2446-2457
[61]Wu H, Yang D, Zhang H. SybilBF:Defending against Sybil Attacks via Bloom Filters. ETRI Journal,2011,33(5):826-829
[62]Ren K, Yu S, Lou W, et al. Multi-user broadcast authentication in wireless sensor networks. IEEE Transactions on Vehicular Technology,2009,58(8):4554-4564
[63]Erode I, Coimbatore I. Optimization of Bloom Filter Using Evolutionary Algorithm. In: Proceedings of the 2012 International Conference on Recent Advances in Computing and Software Systems (RACSS),2012,86-90
[64]Fan L, Cao P, Almeida J, et al. Summary cache:a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking (TON),2000,8(3):281-293
[65]Rousskov A, Wessels D. Cache digests. Computer Networks and ISDN Systems,1998, 30(22-23):2155-2168
[66]Chang F, Dean J, Ghemawat S, et al. Bigtable:A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS),2008,26(2):1-26
[67]Phyu M P, Thein N L. Efficient storage management for distributed storage system. In: Proceedings of the SPIE-The International Society for Optical Engineering 2012, 2012
[68]Li D, Cui H, Hu Y, et al. Scalable data center multicast using multi-class Bloom Filter. In:Proceedings of the 19th IEEE International Conference on Network Protocols,2011, 266-275
[69]Whitaker A, Wetherall D. Forwarding without loops in icarus. In:Proceedings of the Fifth IEEE Conference on Open Architectures and Network Programming,2002,63-75
[70]谢鲲,张大方,谢高岗等.基于轨迹标签的无结构P2P副本一致性维护算法.软件学报,2007,18(1)：105-116
[71]Chang F, Feng W, Li K. Approximate caches for packet classification. In:Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2004,2196-2207
[72]Yu H, Mahapatra R N. A Power and Throughput-Efficient Packet Classifier with n Bloom Filters. IEEE Transactions on Computers,2011,60(8):1182-1193
[73]Dharmapurikar S, Krishnamurthy P, Taylor D E. Longest prefix matching using bloom filters. IEEE/ACM Transactions on Networking (TON),2006,14(2):397-409
[74]Stokes. M. Gnutella2 Specifications Part One. http://www.gnutella2.com/gnutella2_search.htm
[75]谢鲲,张大方,文吉刚等.布鲁姆过滤器代数运算探讨.电子学报,2008,36(5)：869-874
[76]Minsky Y, Trachtenberg A, Zippel R. Set reconciliation with nearly optimal communication complexity. IEEE Information Theory,2003,49(9):2213-2218
[77]Trachtenberg A, Starobinski D, Agarwal S. Fast PDA synchronization using characteristic polynomial interpolation. In:Proceedings of the INFOCOM 2002,2002, 1510-1519
[78]Mitzenmacher M. Compressed bloom filters. IEEE/ACM Transactions on Networking (TON),2002,10(5):604-612
[79]Guo D, Wu J, Chen H, et al. Theory and network applications of dynamic bloom filters. In:Proceedings of the INFOCOM 2006,2006,1-12
[80]Cohen S, Matias Y. Spectral bloom filters. In:Proceedings of the ACM SIGMOD International Conference on Management of Data,2003,241-252
[81]Aguilar-Saborit J, Trancoso P, Muntes-Mulero V, et al. Dynamic count filters. ACM SIGMOD Record,2006,35(1):26-32
[82]Kirsch A, Mitzenmacher M. Distance-sensitive bloom filters. In:Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments,2006,41-50
[83]Ficara D, Giordano S, Procissi G, et al. Multilayer compressed counting bloom filters. In:Proceedings of the INFOCOM 2008,2008,311-315
[84]Shen H, Zhang Y. Improved approximate detection of duplicates for data streams over sliding windows. Journal of Computer Science and Technology,2008,23(6):973-987
[85]Matsumoto Y, Hazeyama H, Kadobayashi Y. Adaptive Bloom filter:A space-efficient counting algorithm for unpredictable network traffic. IEICE transactions on information and systems,2008,91(5):1292-1299
[86]Bruck J, Gao J, Jiang A. Weighted bloom filter. In:Proceedings of the 2006 IEEE International Symposium on Information Theory 2006,2304-2308
[87]Deng F, Rafiei D. Approximately detecting duplicates for streaming data using stable bloom filters. In:Proceedings of the ACM SIGMOD Conference,2006,25-36
[88]Donnet B, Baynat B, Friedman T. Retouched Bloom filters:allowing networked applications to trade off selected false positives against false negatives. In:Proceedings of the 2nd International Conference on Emerging Networking Experiments and Technologies,2006,1-12
[89]Shanmugasundaram K, Bronnimann H, Memon N. Payload attribution via hierarchical bloom filters. In:Proceedings of the 11th ACM Conference on Computer and Communications Security,2004,31-41
[90]肖明忠,代亚非,李晓明.拆分型Bloom Filter.电子学报,2004,32(2)：241-245
[91]Zhong M. Lu P. Shen K, et al. Optimizing data popularity conscious bloom filters. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, 2008,355-364
[92]Ahmadi M, Wong S. A memory-optimized bloom filter using an additional hashing function. In:Proceedings of the Global Communications Conference (GLOBECOM), 2008,2479-2483
[93]Nojima R, Kadobayashi Y. Cryptographically secure bloom-filters. Transactions on Data Privacy,2009,2(2):131-139
[94]Putze F, Sanders P, Singler J. Cache-, hash-and space-efficient bloom filters. In: Proceedings of the 6th International Conference on Experimental Algorithms,2007, 108-121
[95]Bonomi F. Mitzenmacher M, Panigrahy R, et al. An improved construction for counting bloom filters. In:Proceedings of the Algorithms-ESA 2006,2006,684-695
[96]Bonomi F, Mitzenmacher M, Panigrahy R, et al. Bloom filters via d-left hashing and dynamic bit reassignment. In:Proceedings of the 44th Allerton Conference,2006
[97]Lumetta S, Mitzenmacher M. Using the power of two choices to improve Bloom filters. Internet Mathematics,2007,4(1):17-33
[98]Hao F, Kodialam M, Lakshman T. Building high accuracy Bloom filters using partitioned hashing. In:Proceedings of the SIGMETRICS'07,2007,277-288
[99]Charles D, Chellapilla K. Bloomier filters:A second look. In:Proceedings of the 16th Annual European Symposium on Algorithms,2008,259-270
[100]王伟平,李建中,张冬冬等.一种有效的挖掘数据流近似频繁项算法.软件学报,2007,18(4)：884-892
[101]Fang M, Shivakumar N, Garcia-Molina H, et al. Computing Iceberg Queries Efficiently. In:Proceedings of the 24th International Conference on Very Large Data Bases,1999, 299-310
[102]Kumar K, Xu J, Wang J, et al. Space-code bloom filter for efficient per-flow traffic measurement. In:Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement.2004,1762-1773
[103]Witten I, Moffat A, Bell T. Managing Gigabytes, Academic Press,1999
[104]谢鲲,秦拯,文吉刚等.联合多维布鲁姆过滤器查询算法.通信学报,2008,29(1)：56-64
[105]Chazelle B, Kilian J, Rubinfeld R, et al. The Bloomier filter:an efficient data structure for static support lookup tables. In:Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms,2004,30-39
[106]Porat E. An optimal bloom filter replacement based on matrix solving. Computer Science-Theory and Applications,2009:263-273
[107]Mortensen C W, Pagh R, Patraccu M. On dynamic range reporting in one dimension. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, 2005,104-111
[108]Almeida P S, Baquero C, Preguica N, et al. Scalable bloom filters. Information Processing Letters,2007,101(6):255-261
[109]Xie K, Min Y, Zhang D, et al. A scalable Bloom filter for membership queries. In: Proceedings of the IEEE Globecom 2007,2007,543-547
[110]Goodrich M T, Mitzenmacher M. Invertible Bloom lookup tables. In:Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton),2011,792-799
[111]Eppstein D, Goodrich M T. Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters. IEEE Transaction on Knowledge and Data Engineering,2011,23(2):297-306
[112]Laufer R P, Velloso P B, Duarte O C.A Generalized Bloom Filter to secure distributed network applications. Computer Networks,2011,55(8):1804-1819
[113]Rothenberg C E, Macapuna C A B, Verdi F L, et al. The deletable Bloom filter:a new member of the Bloom family. Communications Letters, IEEE,2010,14(6):557-559
[114]http://www.squid-cache.org/
[115]Marais H, Bharat K. Supporting cooperative and personal surfing with a desktop assistant. In:Proceedings of the 10th Annual ACM Symposium on User Interface Software and Technology,1997,129-138
[116]Cai H, Ge P, Wang J. Applications of Bloom filters in peer-to-peer systems:Issues and questions. In:Proceedings of the International Conference on Networking, Architecture, and Storage,2008,97-103
[117]Cuenca-Acuna F M, Peery C, Martin R P, et al. Planetp:Using gossiping to build content addressable peer-to-peer information sharing communities. In:Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, 2003,236-246
[118]Cai H, Wang J. Exploiting geographical and temporal locality to boost search efficiency in peer-to-peer systems. IEEE Transactions on Parallel and Distributed Systems,2006,17(10):1189-1203
[119]Pouwelse J A, Garbacki P, Wang J, et al. TRIBLER:a social-based peer-to-peer system. Concurrency and Computation:Practice and Experience,2008,20(2):127-138
[120]Broder A. Mitzenmacher M. Using multiple hash functions to improve IP lookups. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2001,1454-1463
[121]GrtinvaU B. Scalable multicast forwarding. SIGCOMM Computer Communications Review,2002,32(1):68-68
[122]Yu M, Fabrikant A, Rexford J. BUFFALO:Bloom filter forwarding architecture for large organizations. In:Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies,2009,313-324
[123]Sarela M, Rothenberg C E, Aura T, et al. Forwarding anomalies in Bloom filter-based multicast. In:Proceedings of the IEEE INFOCOM 2011,2011,2399-2407
[124]Tian X, Cheng Y. Loop Mitigation in Bloom Filter Based Multicast:A Destination-Oriented Approach. In:Proceedings of the IEEE INFOCOM 2012,2012, 2131-2139
[125]Zhao Y, Wu J. ZigZag:A Content-based Publish/Subscribe Architecture for Human Networks. In:Proceedings of the 20th International Conference on Computer Communications and Networks (ICCCN),2011,1-6
[126]Bonomi F, Mitzenmacher M, Panigrah R, et al. Beyond bloom filters:from approximate membership checks to approximate state machines. ACM SIGCOMM Computer Communication Review,2006,36(4):315-326
[127]Hsiao P H. Geographical region summary service for geographical routing. ACM SIGMOBILE Mobile Computing and Communications Review,2001,5(4):25-39
[128]Takiguchi T, Saruwatari S, Morito T, et al. A novel wireless wake-up mechanism for energy-efficient ubiquitous networks. In:Proceedings of the 1st International Workshop on Green Communications,2009
[129]Gong X, Qian W, Yan Y, et al. Bloom filter-based XML packets filtering for millions of path queries. In:Proceedings of the 21st International Conference on Data Engineering, 2005,890-901
[130]Nohara Y, Inoue S, Yasuura H. A secure high-speed identification scheme for RFID using Bloom filters. In:Proceedings of the Third International Conference on Availability, Reliability and Security,2008,111-122
[131]Hua Y, Feng D, Xie T. Multi-dimensional range query for data management using bloom filters. In:Proceedings of the IEEE International Conference on Cluster Computing,2007,428-433
[132]Blake G, Dreslinski R G, Mudge T. Bloom filter guided transaction scheduling. In: Proceedings of the IEEE 17th International Symposium on High Performance Computer Architecture (HPCA),2011,75-86
[133]Atcheson B, Heidrich W. Non-parametric acquisition of near-dirac pixel correspondences. In:Proceedings of the International Conference on Computer Vision Theory and Applications,2012,247-254
[134]Kubiatowicz J, Bindel D, Chen Y, et al. Oceanstore:An architecture for global-scale persistent storage. ACM Sigplan Notices,2000,35(11):190-201
[135]Rowstron A, Druschel P. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In:Proceedings of the Eighteenth ACM Symposium on Operations Systems Principles,2001,188-201
[136]Ratnasamy S, Francis P, Handley M, et al. A scalable content-addressable network. ACM SIGCOMM Computer Communication Review,2001,31(4):161-172
[137]Stoica I, Morris R, Karger D, et al. Chord:A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review,2001, 31(4):149-160
[138]Choi M Y, Cho E A, Park D H, et al. A Synchronization Algorithm of Mobile Database for Ubiquitous Computing. In:Proceedings of the 2009 Fifth International Joint Conference on INC, IMS and IDC,2009,416-419
[139]Leitao J, Van Renesse R, Rodrigues L. Balancing gossip exchanges in networks with firewalls. In:Proceedings of the 9th international conference on Peer-to-peer systems, 2010,7-7
[140]Cheng S, Chang C K, Zhang L J. An efficient service discovery algorithm for counting bloom filter-based service registry. In:Proceedings of the 2009 IEEE International Conference on Web Services,2009,157-164
[141]Burrows J H. Secure hash standard, DTIC Document,1995
[142]Minsky Y, Trachtenberg A. Practical set reconciliation, Boston University,2002
[143]Byers J, Considine J, Mitzenmacher M. Fast approximate reconciliation of set differences, Boston University,2002
[144]Demers A, Greene D, Hauser C, et al. Epidemic algorithms for replicated database maintenance. In:Proceedings of the 6th ACM Symp. on Principles of Distributed Computing,1987,1-12
[145]Terry D B, Theimer M M, Petersen K, et al. Managing update conflicts in Bayou, a weakly connected replicated storage system. In:Proceedings of the 15th Symposium on Operating Systems Principles,1995,172-182
[146]Ratner D, Reiher P, Popek G, et al. Peer replication with selective control. In: Proceedings of the First International Conference on Mobile Data Access,1999, 169-181
[147]Cetintemel U, Keleher P J, Franklin M J. Support for speculative update propagation and mobility in deno. In:Proceedings of the 22nd International Conference on Distributed Computing Systems,2001,509-516
[148]Ahluwalia M, Gupta R, Gangopadhyay A, et al. Target-based database synchronization. In:Proceedings of the 2010 ACM Symposium on Applied Computing,2010, 1643-1647
[149]付波,李建平,文晓阳.基于集合调和的远程口令恢复方法.计算机应用研究,2009,26(6)：2113-2116
[150]Elkouss D, Martinez J, Lancho D, et al. Rate compatible protocol for information reconciliation:An application to QKD. In:Proceedings of the Information Theory Workshop (ITW),2010,145-149
[151]Elkouss D, Martinez-Mateo J, Martin V. Secure rate-adaptive reconciliation. In: Proceedings of the 2010 International Symposium on Information Theory and its Applications (ISITA),2010,179-184
[152]Guo K, Hayden M, Van Renesse R, et al. GSGC:An Efficient Gossip-Style Garbage Collection Scheme for Scalable Reliable Multicast, Cornell University,1997
[153]Van Renesse R. Scalable and secure resource location. In:Proceedings of the International Conference on System Sciences,2000,1530-1605
[154]Zhu B, Li K, Patterson H. Avoiding the disk bottleneck in the data domain deduplication file system. In:Proceedings of the 6th USENIX Conference on File and Storage Technologies,2008,1-14
[155]Kulkarni P, Douglis F, LaVoie J, et al. Redundancy elimination within large collections of files. In:Proceedings of the annual conference on USENIX Annual Technical Conference,2004
[156]Bolosky W J, Corbin S, Goebel D, et al. Single instance storage in Windows 2000. In: Proceedings of the 4th conference on USENIX Windows Systems Symposium,2000
[157]Byers J W, Luby M, Mitzenmacher M. Accessing multiple mirror sites in parallel: Using Tornado codes to speed up downloads. In:Proceedings of the IEEE INFOCOM 1999,1999,275-283
[158]Agarwal S, Trachtenberg A. Approximating the number of differences between remote sets. In:Proceedings of the Information Theory Workshop,2006,217-221
[159]Chen H H, Jin H, Wang J, et al. Efficient multi-keyword search over p2p web. In: Proceedings of the 17th International Conference on World Wide Web,2008,989-998
[160]Zegura E W, Calvert K L, Bhattacharjee S. How to model an internetwork. In: Proceedings of the INFOCOM 1996,1996,594-602
[161]Karpovsky M G, Levitin L B, Trachtenberg A. Data verification and reconciliation with generalized error-control codes. IEEE Transactions on Information Theory,2003,49(7): 1788-1793
[162]Orlitsky A. Communication issues in distributed computing, Stanford University. Ph. D, 1986
[2]徐恪等.新一代互联网体系结构可演进性研究进展.见：中国计算机科学技术发展报告2010.北京：机械工业出版社,2011,72-101
[3]任丰原,林闯.无线传感器网络的现状与发展.见：中国计算机科学技术发展报告2005.北京：清华大学出版社,2006,110-127
[4]张为民等.云计算深刻改变未来.北京：科学出版社,2009
[5]冯丹等.海量存储系统及技术研究进展.见：中国计算机科学技术发展报告2010.北京：机械工业出版社,2011,46-71
[6]中国互联网络信息中心.第30次中国互联网络发展状况统计报告,http://www. cnnic.org.cn/hlwfzyj/hlwxzbg/hlwtjbg/201207/t20120723_32497.htm,2012.7.19
[7]大数据时代降临.http://today.banyuetan.org/jrt/120922/70953.shtml
[8]Bloom B H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM,1970,13(7):422-426
[9]Tarkoma S, Rothenberg C, Lagerspetz E. Theory and practice of bloom filters for distributed systems. IEEE Communications Surveys & Tutorials,2012,14(1):131-155
[10]Jerzak Z, Fetzer C. Bloom filter based routing for content-based publish/subscribe. In: Proceedings of the Second International Conference on Distributed Event-based Systems,2008,71-81
[11]Byers J, Considine J, Mitzenmacher M, et al. Informed content delivery across adaptive overlay networks. ACM SIGCOMM Computer Communication Review,2002,32(4): 47-60
[12]Abdel-Ghaffar K A S, El Abbadi A. An optimal strategy for comparing file copies. IEEE Transactions on Parallel and Distributed Systems,1994,5(1):87-93
[13]Starobinski D, Trachtenberg A, Agarwal S. Efficient PDA synchronization. IEEE Transactions on Mobile Computing,2003,2(1):40-51
[14]Reynolds P, Vahdat A. Efficient peer-to-peer keyword searching. In:Proceedings of the middleware 2003, Lecture Notes in Computer Science,2003,21-40
[15]Czerwinski S E, Zhao B Y, Hodes T D, et al. An architecture for a secure service discovery service. In:Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking,1999,24-35
[16]Rhea S, Kubiatowicz J. Probabilistic location and routing. In:Proceedings of the INFOCOM 2002,2002,1248-1257
[17]Mullin J K, Margoliash D J. A tale of three spelling checkers. Software:Practice and Experience,1990,20(6):625-630
[18]McIlroy M. Development of a spelling list. IEEE Transactions on Communications, 1982,30(1):91-99
[19]Spafford E H. Opus:Preventing weak password choices. Computers & Security,1992, 11(3):273-278
[20]Manber U, Wu S. An algorithm for approximate membership checking with application to password security. Information Processing Letters,1994,50(4):191-197
[21]Bratbergsengen K. Hashing Hethods And Relational Algebra Operations. In: Proceedings of the tenth International Conference on Very Large Databases,1984, 323-333
[22]Valduriez P, Gardarin G. Join and semijoin algorithms for a multiprocessor database machine. ACM Transactions on Database Systems (TODS),1984,9(1):133-161
[23]Mackert L F. R* optimizer validation and performance evaluation for distributed queries. In:Proceedings of the Twelfth International Conference on Very Large Databases,1988,149-159
[24]Mullin J K. Optimal semijoins for distributed database systems. IEEE Transactions on Software Engineering,1990,16(5):558-560
[25]Mullin J K. Estimating the size of a relational join. Information Systems,1993,18(3): 189-196
[26]Gremillion L L. Designing a Bloom filter for differential file access. Communications of the ACM,1982,25(9):600-604
[27]Mullin J K. A second look at Bloom filters. Communications of the ACM,1983,26(8): 570-571
[28]Kim Y, Cho K, Yoon J, et al. Using Bloom Filters for Mining Top-k Frequent Itemsets in Data Streams. Secure and Trust Computing, Data Management and Applications. J. J. Park, J. Lopez, S.-S. Yeo, T. Shon and D. Taniar, Springer Berlin Heidelberg.2011,186: 209-216
[29]Aditya T, Baruah P, Mukkamala R. Employing Bloom Filters for Enforcing Integrity of Outsourced Databases in Cloud Environments. Advances in Computing and Communications,2011:446-460
[30]谢鲲,文吉刚,张大方等.布鲁姆过滤器查询算法.软件学报,2009,20(1)：96-108
[31]Broder A, Mitzenmacher M. Network applications of bloom filters:A survey. Internet Mathematics,2005,1(4):485-509
[32]Song H, Dharmapurikar S, Turner J, et al. Fast hash table lookup using extended bloom filter:an aid to network processing. In:Proceedings of the SIGCOMM'05,2005, 181-192
[33]Song H, Hao F, Kodialam M, et al. Ipv6 lookups using distributed and load balanced bloom filters for 100gbps core router line cards. In:Proceedings of the INFOCOM 2009,2009,2518-2526
[34]Dharmapurikar S, Krishnamurthy P, Sproull T, et al. Deep packet inspection using parallel bloom filters. In:Proceedings of the 11th Symposium on High Performance Interconnects,2003,44-51
[35]Chen Y, Oguntoyinbo O. Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks. Computer Communications, 2009,32(2):349-356
[36]Dharmapurikar S, Song H, Turner J, et al. Fast packet classification using bloom filters. In:Proceedings of the 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems,2006,61-70
[37]Ahmadi M, Wong S. Modified collision packet classification using counting bloom filter in tuple space. In:Proceedings of the 25th IASTED Conference on Parallel and Distributed Computing and Networks,2007,315-320
[38]谢鲲,赵姣姣,张大方等.基于计数布鲁姆过滤器的快速多维包分类算法.电子学报,2010,38(5)：1046-1052
[39]Estan C, Varghese G. New directions in traffic measurement and accounting. In: Proceedings of the ACM SIGCOMM 2002,2002,323-336
[40]Feng W, Shin K G, Kandlur D D, et al. The BLUE active queue management algorithms. IEEE/ACM Transactions on Networking (TON),2002,10(4):513-528
[41]吴桦,龚俭,杨望.一种基于双重Counter Bloom Filter的长流识别算法.软件学报,2010,21(5)：1115-1126
[42]Zhao Q G, Ogihara M, Wang H, et al. Finding global icebergs over distributed data sets. In:Proceedings of the Twentyfifth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,2006,298-307
[43]Laufer R P, Velloso P B, de O Cunha D, et al. Towards stateless single-packet IP traceback. In:Proceedings of the 32nd IEEE Conference on Local Computer Networks, 2007,548-555
[44]Snoeren A C, Partridge C, Sanchez L A, et al. Single-packet IP traceback. IEEE/ACM Transactions on Networking (TON),2002,10(6):721-734
[45]Snoeren A C, Partridge C, Sanchez L A, et al. Hash-based IP traceback. In:Proceedings of the 2001 SIGCOMM Conference,2001,3-14
[46]Pang M, Xu G. A personalized search engine research based on Bloom filter. In: Proceedings of the 2011 International Conference on Electric Engineering and Computer (MEC),2011,2365-2368
[47]He W, Lv T. Bloom filter-based keyword search over XML data in structured Peer-to-Peer systems. In:Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology,2010,177-181
[48]Kumar A, Xu J, Zegura E W. Efficient and scalable query routing for unstructured peer-to-peer networks. In:Proceedings of the INFOCOM 2005,2005,1162-1173
[49]Minsky Y, Trachtenberg A. Efficient reconciliation of unordered databases, Cornell University,1999
[50]Eppstein D, Goodrich M T, Uyeda F, et al. What's the difference?Efficient set reconciliation without prior context. In:Proceedings of the ACM SIGCOMM 2011, 2011,218-229
[51]Skjegstad M, Maseng T. Low complexity set reconciliation using Bloom filters. In: Proceedings of the 7th ACM ACM SIGACT/SIGMOBILE International Workshop on Foundations of Mobile Computing,2011,33-41
[52]Zhao T, Liu Z, Yan W, et al. BFBD:A Bloom Filter based Buffering Data Dissemination algorithm for Vehicular Ad hoc Networks. In:Proceedings of the 2011 IEEE Consumer Communications and Networking Conference (CCNC),2011, 447-481
[53]Melsted P, Pritchard J K. Efficient counting of k-mers in DNA sequences using a bloom filter. BMC bioinformatics,2011,12(1):1-7
[54]Ma L, Chamberlain R D, Buhler J D, et al. Bloom Filter Performance on Graphics Engines. In:Proceedings of the 2011 International Conference on Parallel Processing, 2011,522-531
[55]肖军,云晓春,张永铮.随机伪造源地址分布式拒绝服务攻击过滤.软件学报,2011,22(10)：2425-2437
[56]Bellovin S M, Cheswick W R. Privacy-enhanced searches using encrypted bloom filters, Columbia University and AT&T,2004
[57]Antichi G, Ficara D, Giordano S, et al. Counting bloom filters for pattern matching and anti-evasion at the wire speed. IEEE Network,2009,23(1):30-35
[58]Ballani H, Chawathe Y, Ratnasamy S, et al. Off by default! In:Proceedings of the 4th ACM Workshop on Hot Topics in Networks (Hotnets-IV),2005
[59]Wang X F, Reiter M K. Mitigating bandwidth-exhaustion attacks using congestion puzzles. In:Proceedings of the 11th ACM Conference on Computer and Communications Security,2004,257-267
[60]Ye F, Luo H, Lu S, et al. Statistical en-route filtering of injected false data in sensor networks. In:Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2004,2446-2457
[61]Wu H, Yang D, Zhang H. SybilBF:Defending against Sybil Attacks via Bloom Filters. ETRI Journal,2011,33(5):826-829
[62]Ren K, Yu S, Lou W, et al. Multi-user broadcast authentication in wireless sensor networks. IEEE Transactions on Vehicular Technology,2009,58(8):4554-4564
[63]Erode I, Coimbatore I. Optimization of Bloom Filter Using Evolutionary Algorithm. In: Proceedings of the 2012 International Conference on Recent Advances in Computing and Software Systems (RACSS),2012,86-90
[64]Fan L, Cao P, Almeida J, et al. Summary cache:a scalable wide-area web cache sharing protocol. IEEE/ACM Transactions on Networking (TON),2000,8(3):281-293
[65]Rousskov A, Wessels D. Cache digests. Computer Networks and ISDN Systems,1998, 30(22-23):2155-2168
[66]Chang F, Dean J, Ghemawat S, et al. Bigtable:A distributed storage system for structured data. ACM Transactions on Computer Systems (TOCS),2008,26(2):1-26
[67]Phyu M P, Thein N L. Efficient storage management for distributed storage system. In: Proceedings of the SPIE-The International Society for Optical Engineering 2012, 2012
[68]Li D, Cui H, Hu Y, et al. Scalable data center multicast using multi-class Bloom Filter. In:Proceedings of the 19th IEEE International Conference on Network Protocols,2011, 266-275
[69]Whitaker A, Wetherall D. Forwarding without loops in icarus. In:Proceedings of the Fifth IEEE Conference on Open Architectures and Network Programming,2002,63-75
[70]谢鲲,张大方,谢高岗等.基于轨迹标签的无结构P2P副本一致性维护算法.软件学报,2007,18(1)：105-116
[71]Chang F, Feng W, Li K. Approximate caches for packet classification. In:Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2004,2196-2207
[72]Yu H, Mahapatra R N. A Power and Throughput-Efficient Packet Classifier with n Bloom Filters. IEEE Transactions on Computers,2011,60(8):1182-1193
[73]Dharmapurikar S, Krishnamurthy P, Taylor D E. Longest prefix matching using bloom filters. IEEE/ACM Transactions on Networking (TON),2006,14(2):397-409
[74]Stokes. M. Gnutella2 Specifications Part One. http://www.gnutella2.com/gnutella2_search.htm
[75]谢鲲,张大方,文吉刚等.布鲁姆过滤器代数运算探讨.电子学报,2008,36(5)：869-874
[76]Minsky Y, Trachtenberg A, Zippel R. Set reconciliation with nearly optimal communication complexity. IEEE Information Theory,2003,49(9):2213-2218
[77]Trachtenberg A, Starobinski D, Agarwal S. Fast PDA synchronization using characteristic polynomial interpolation. In:Proceedings of the INFOCOM 2002,2002, 1510-1519
[78]Mitzenmacher M. Compressed bloom filters. IEEE/ACM Transactions on Networking (TON),2002,10(5):604-612
[79]Guo D, Wu J, Chen H, et al. Theory and network applications of dynamic bloom filters. In:Proceedings of the INFOCOM 2006,2006,1-12
[80]Cohen S, Matias Y. Spectral bloom filters. In:Proceedings of the ACM SIGMOD International Conference on Management of Data,2003,241-252
[81]Aguilar-Saborit J, Trancoso P, Muntes-Mulero V, et al. Dynamic count filters. ACM SIGMOD Record,2006,35(1):26-32
[82]Kirsch A, Mitzenmacher M. Distance-sensitive bloom filters. In:Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments,2006,41-50
[83]Ficara D, Giordano S, Procissi G, et al. Multilayer compressed counting bloom filters. In:Proceedings of the INFOCOM 2008,2008,311-315
[84]Shen H, Zhang Y. Improved approximate detection of duplicates for data streams over sliding windows. Journal of Computer Science and Technology,2008,23(6):973-987
[85]Matsumoto Y, Hazeyama H, Kadobayashi Y. Adaptive Bloom filter:A space-efficient counting algorithm for unpredictable network traffic. IEICE transactions on information and systems,2008,91(5):1292-1299
[86]Bruck J, Gao J, Jiang A. Weighted bloom filter. In:Proceedings of the 2006 IEEE International Symposium on Information Theory 2006,2304-2308
[87]Deng F, Rafiei D. Approximately detecting duplicates for streaming data using stable bloom filters. In:Proceedings of the ACM SIGMOD Conference,2006,25-36
[88]Donnet B, Baynat B, Friedman T. Retouched Bloom filters:allowing networked applications to trade off selected false positives against false negatives. In:Proceedings of the 2nd International Conference on Emerging Networking Experiments and Technologies,2006,1-12
[89]Shanmugasundaram K, Bronnimann H, Memon N. Payload attribution via hierarchical bloom filters. In:Proceedings of the 11th ACM Conference on Computer and Communications Security,2004,31-41
[90]肖明忠,代亚非,李晓明.拆分型Bloom Filter.电子学报,2004,32(2)：241-245
[91]Zhong M. Lu P. Shen K, et al. Optimizing data popularity conscious bloom filters. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, 2008,355-364
[92]Ahmadi M, Wong S. A memory-optimized bloom filter using an additional hashing function. In:Proceedings of the Global Communications Conference (GLOBECOM), 2008,2479-2483
[93]Nojima R, Kadobayashi Y. Cryptographically secure bloom-filters. Transactions on Data Privacy,2009,2(2):131-139
[94]Putze F, Sanders P, Singler J. Cache-, hash-and space-efficient bloom filters. In: Proceedings of the 6th International Conference on Experimental Algorithms,2007, 108-121
[95]Bonomi F. Mitzenmacher M, Panigrahy R, et al. An improved construction for counting bloom filters. In:Proceedings of the Algorithms-ESA 2006,2006,684-695
[96]Bonomi F, Mitzenmacher M, Panigrahy R, et al. Bloom filters via d-left hashing and dynamic bit reassignment. In:Proceedings of the 44th Allerton Conference,2006
[97]Lumetta S, Mitzenmacher M. Using the power of two choices to improve Bloom filters. Internet Mathematics,2007,4(1):17-33
[98]Hao F, Kodialam M, Lakshman T. Building high accuracy Bloom filters using partitioned hashing. In:Proceedings of the SIGMETRICS'07,2007,277-288
[99]Charles D, Chellapilla K. Bloomier filters:A second look. In:Proceedings of the 16th Annual European Symposium on Algorithms,2008,259-270
[100]王伟平,李建中,张冬冬等.一种有效的挖掘数据流近似频繁项算法.软件学报,2007,18(4)：884-892
[101]Fang M, Shivakumar N, Garcia-Molina H, et al. Computing Iceberg Queries Efficiently. In:Proceedings of the 24th International Conference on Very Large Data Bases,1999, 299-310
[102]Kumar K, Xu J, Wang J, et al. Space-code bloom filter for efficient per-flow traffic measurement. In:Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement.2004,1762-1773
[103]Witten I, Moffat A, Bell T. Managing Gigabytes, Academic Press,1999
[104]谢鲲,秦拯,文吉刚等.联合多维布鲁姆过滤器查询算法.通信学报,2008,29(1)：56-64
[105]Chazelle B, Kilian J, Rubinfeld R, et al. The Bloomier filter:an efficient data structure for static support lookup tables. In:Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms,2004,30-39
[106]Porat E. An optimal bloom filter replacement based on matrix solving. Computer Science-Theory and Applications,2009:263-273
[107]Mortensen C W, Pagh R, Patraccu M. On dynamic range reporting in one dimension. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, 2005,104-111
[108]Almeida P S, Baquero C, Preguica N, et al. Scalable bloom filters. Information Processing Letters,2007,101(6):255-261
[109]Xie K, Min Y, Zhang D, et al. A scalable Bloom filter for membership queries. In: Proceedings of the IEEE Globecom 2007,2007,543-547
[110]Goodrich M T, Mitzenmacher M. Invertible Bloom lookup tables. In:Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton),2011,792-799
[111]Eppstein D, Goodrich M T. Straggler Identification in Round-Trip Data Streams via Newton's Identities and Invertible Bloom Filters. IEEE Transaction on Knowledge and Data Engineering,2011,23(2):297-306
[112]Laufer R P, Velloso P B, Duarte O C.A Generalized Bloom Filter to secure distributed network applications. Computer Networks,2011,55(8):1804-1819
[113]Rothenberg C E, Macapuna C A B, Verdi F L, et al. The deletable Bloom filter:a new member of the Bloom family. Communications Letters, IEEE,2010,14(6):557-559
[114]http://www.squid-cache.org/
[115]Marais H, Bharat K. Supporting cooperative and personal surfing with a desktop assistant. In:Proceedings of the 10th Annual ACM Symposium on User Interface Software and Technology,1997,129-138
[116]Cai H, Ge P, Wang J. Applications of Bloom filters in peer-to-peer systems:Issues and questions. In:Proceedings of the International Conference on Networking, Architecture, and Storage,2008,97-103
[117]Cuenca-Acuna F M, Peery C, Martin R P, et al. Planetp:Using gossiping to build content addressable peer-to-peer information sharing communities. In:Proceedings of the 12th IEEE International Symposium on High Performance Distributed Computing, 2003,236-246
[118]Cai H, Wang J. Exploiting geographical and temporal locality to boost search efficiency in peer-to-peer systems. IEEE Transactions on Parallel and Distributed Systems,2006,17(10):1189-1203
[119]Pouwelse J A, Garbacki P, Wang J, et al. TRIBLER:a social-based peer-to-peer system. Concurrency and Computation:Practice and Experience,2008,20(2):127-138
[120]Broder A. Mitzenmacher M. Using multiple hash functions to improve IP lookups. In: Proceedings of the 20th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),2001,1454-1463
[121]GrtinvaU B. Scalable multicast forwarding. SIGCOMM Computer Communications Review,2002,32(1):68-68
[122]Yu M, Fabrikant A, Rexford J. BUFFALO:Bloom filter forwarding architecture for large organizations. In:Proceedings of the 5th International Conference on Emerging Networking Experiments and Technologies,2009,313-324
[123]Sarela M, Rothenberg C E, Aura T, et al. Forwarding anomalies in Bloom filter-based multicast. In:Proceedings of the IEEE INFOCOM 2011,2011,2399-2407
[124]Tian X, Cheng Y. Loop Mitigation in Bloom Filter Based Multicast:A Destination-Oriented Approach. In:Proceedings of the IEEE INFOCOM 2012,2012, 2131-2139
[125]Zhao Y, Wu J. ZigZag:A Content-based Publish/Subscribe Architecture for Human Networks. In:Proceedings of the 20th International Conference on Computer Communications and Networks (ICCCN),2011,1-6
[126]Bonomi F, Mitzenmacher M, Panigrah R, et al. Beyond bloom filters:from approximate membership checks to approximate state machines. ACM SIGCOMM Computer Communication Review,2006,36(4):315-326
[127]Hsiao P H. Geographical region summary service for geographical routing. ACM SIGMOBILE Mobile Computing and Communications Review,2001,5(4):25-39
[128]Takiguchi T, Saruwatari S, Morito T, et al. A novel wireless wake-up mechanism for energy-efficient ubiquitous networks. In:Proceedings of the 1st International Workshop on Green Communications,2009
[129]Gong X, Qian W, Yan Y, et al. Bloom filter-based XML packets filtering for millions of path queries. In:Proceedings of the 21st International Conference on Data Engineering, 2005,890-901
[130]Nohara Y, Inoue S, Yasuura H. A secure high-speed identification scheme for RFID using Bloom filters. In:Proceedings of the Third International Conference on Availability, Reliability and Security,2008,111-122
[131]Hua Y, Feng D, Xie T. Multi-dimensional range query for data management using bloom filters. In:Proceedings of the IEEE International Conference on Cluster Computing,2007,428-433
[132]Blake G, Dreslinski R G, Mudge T. Bloom filter guided transaction scheduling. In: Proceedings of the IEEE 17th International Symposium on High Performance Computer Architecture (HPCA),2011,75-86
[133]Atcheson B, Heidrich W. Non-parametric acquisition of near-dirac pixel correspondences. In:Proceedings of the International Conference on Computer Vision Theory and Applications,2012,247-254
[134]Kubiatowicz J, Bindel D, Chen Y, et al. Oceanstore:An architecture for global-scale persistent storage. ACM Sigplan Notices,2000,35(11):190-201
[135]Rowstron A, Druschel P. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. In:Proceedings of the Eighteenth ACM Symposium on Operations Systems Principles,2001,188-201
[136]Ratnasamy S, Francis P, Handley M, et al. A scalable content-addressable network. ACM SIGCOMM Computer Communication Review,2001,31(4):161-172
[137]Stoica I, Morris R, Karger D, et al. Chord:A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review,2001, 31(4):149-160
[138]Choi M Y, Cho E A, Park D H, et al. A Synchronization Algorithm of Mobile Database for Ubiquitous Computing. In:Proceedings of the 2009 Fifth International Joint Conference on INC, IMS and IDC,2009,416-419
[139]Leitao J, Van Renesse R, Rodrigues L. Balancing gossip exchanges in networks with firewalls. In:Proceedings of the 9th international conference on Peer-to-peer systems, 2010,7-7
[140]Cheng S, Chang C K, Zhang L J. An efficient service discovery algorithm for counting bloom filter-based service registry. In:Proceedings of the 2009 IEEE International Conference on Web Services,2009,157-164
[141]Burrows J H. Secure hash standard, DTIC Document,1995
[142]Minsky Y, Trachtenberg A. Practical set reconciliation, Boston University,2002
[143]Byers J, Considine J, Mitzenmacher M. Fast approximate reconciliation of set differences, Boston University,2002
[144]Demers A, Greene D, Hauser C, et al. Epidemic algorithms for replicated database maintenance. In:Proceedings of the 6th ACM Symp. on Principles of Distributed Computing,1987,1-12
[145]Terry D B, Theimer M M, Petersen K, et al. Managing update conflicts in Bayou, a weakly connected replicated storage system. In:Proceedings of the 15th Symposium on Operating Systems Principles,1995,172-182
[146]Ratner D, Reiher P, Popek G, et al. Peer replication with selective control. In: Proceedings of the First International Conference on Mobile Data Access,1999, 169-181
[147]Cetintemel U, Keleher P J, Franklin M J. Support for speculative update propagation and mobility in deno. In:Proceedings of the 22nd International Conference on Distributed Computing Systems,2001,509-516
[148]Ahluwalia M, Gupta R, Gangopadhyay A, et al. Target-based database synchronization. In:Proceedings of the 2010 ACM Symposium on Applied Computing,2010, 1643-1647
[149]付波,李建平,文晓阳.基于集合调和的远程口令恢复方法.计算机应用研究,2009,26(6)：2113-2116
[150]Elkouss D, Martinez J, Lancho D, et al. Rate compatible protocol for information reconciliation:An application to QKD. In:Proceedings of the Information Theory Workshop (ITW),2010,145-149
[151]Elkouss D, Martinez-Mateo J, Martin V. Secure rate-adaptive reconciliation. In: Proceedings of the 2010 International Symposium on Information Theory and its Applications (ISITA),2010,179-184
[152]Guo K, Hayden M, Van Renesse R, et al. GSGC:An Efficient Gossip-Style Garbage Collection Scheme for Scalable Reliable Multicast, Cornell University,1997
[153]Van Renesse R. Scalable and secure resource location. In:Proceedings of the International Conference on System Sciences,2000,1530-1605
[154]Zhu B, Li K, Patterson H. Avoiding the disk bottleneck in the data domain deduplication file system. In:Proceedings of the 6th USENIX Conference on File and Storage Technologies,2008,1-14
[155]Kulkarni P, Douglis F, LaVoie J, et al. Redundancy elimination within large collections of files. In:Proceedings of the annual conference on USENIX Annual Technical Conference,2004
[156]Bolosky W J, Corbin S, Goebel D, et al. Single instance storage in Windows 2000. In: Proceedings of the 4th conference on USENIX Windows Systems Symposium,2000
[157]Byers J W, Luby M, Mitzenmacher M. Accessing multiple mirror sites in parallel: Using Tornado codes to speed up downloads. In:Proceedings of the IEEE INFOCOM 1999,1999,275-283
[158]Agarwal S, Trachtenberg A. Approximating the number of differences between remote sets. In:Proceedings of the Information Theory Workshop,2006,217-221
[159]Chen H H, Jin H, Wang J, et al. Efficient multi-keyword search over p2p web. In: Proceedings of the 17th International Conference on World Wide Web,2008,989-998
[160]Zegura E W, Calvert K L, Bhattacharjee S. How to model an internetwork. In: Proceedings of the INFOCOM 1996,1996,594-602
[161]Karpovsky M G, Levitin L B, Trachtenberg A. Data verification and reconciliation with generalized error-control codes. IEEE Transactions on Information Theory,2003,49(7): 1788-1793
[162]Orlitsky A. Communication issues in distributed computing, Stanford University. Ph. D, 1986