Abstract: 结合二项分布和小概率原理进行理论推导,提出了Minwise Hash的动态双重阈值过滤器,将比对过程划分为多个比对点,并设置各比对点的动态阈值,过滤相似度低于下界阈值TL(k)的文档,输出相似度高于上界阈值Tu(k)的文档.该提前过滤的方法减少了后续的比对次数,降低了工作量,并设计了多组实验,结果显示过滤器在选取了适当的参数时,计算时间仅为原Minwise Hash的31％或原b位Minwise Hash的36％,较大地提升了原算法的时间效率.动态双重阈值过滤器不仅能应用于Minwise Hash,也能用于它的变种算法(如b位Minwise Hash),乃至所有符合二项分布的估计子.

Key words: 动态双重阈值, 相似性检测, 哈希, 小概率事件