【摘要】 提出了一种基于计数布鲁姆过滤器的集合调和方法,该方法将远程节点A和B上的数据集合SA和SB分别用计数布鲁姆过滤器表示,设为CBF(SA)和CBF(SB),节点A将CBF(SA)发送给节点B,节点B进行计数布鲁姆过滤器减运算,得到差过滤器CBF(SB)CBF(SA),然后利用CBF(SB)CBF(SA)查询并获得集合SB中的差集元素SB SA,并返回SB SA给节点A,最后节点A用差集SB SA和自身集合SA进行集合并运算,完成集合调和。由于计数布鲁姆过滤器支持集合元素的删除操作,因此,该方法非常适合应用于数据集合更新频繁的分布式系统。理论分析和仿真实验结果表明,该方法既具有精确集合调和,能得到全部SB SA元素的优点,也具有近似集合调和仅需单轮消息交换的优点。更多还原

【Abstract】 A new set reconciliation algorithm was presented,which called counting-Bloom-filter based set reconcilia-tion(CBFSR).This method represented sets SA and SB as counting Bloom filters,subtracts SA’s counting Bloom filter from SB’s counting Bloom filter,the differences denoted CBF(SB)?CBF(SA),then determined SB?SA elements in SB with CBF(SB)?CBF(SA),and finally performed union operation on SB?SA and SA.Simulation resdts show count-ing-Bloom-filter based set reconciliation combines the advantages of exact set reconciliation and approximate set recon-ciliation,besides gaining all SB?SA elements with single-round messgage exchanges,it can apply to update-intensive dis-tributed systems because counting Bloom filters support element deletion operation.更多还原