基于Bloom filter的远程对称差规模估算法

Bloom Filter-based Estimating Methods for the Number of Differences Between Remote Sets

在内容分发网络、闲谈协议、移动数据同步等分布式系统中,远程主机上集合对称差规模的估算准确程度,直接影响基于CPISync算法的集合调和方法的消息交换轮数以及调和时间。对称差规模的估算误差越低,则集合调和的速度越快。本文提出基于布鲁姆过滤器的准交集查询法,该算法可显著降低对称差规模的估算误差,提高调和算法的效率。

The problem of estimating the number of symmetric differences between sets held on remote hosts is impor tant for distributed applications such as data synchronizations in content delivery networks, gossip protocols and mobile net- works. Estimating accuracy affects directly the performance of CPISync-based set reconciliation algorithms. Less error dur- ing estimating procedure yields faster reconciliation rate. Quasi-intersection query method is a new bloom filter-based estima ting method. It can significantly reduce errors for estimating the number of symmetric differences and improve reconciliation efficiency of reconciliation algorithms.