Journal of Shanghai Jiao Tong University

Journal of Shanghai Jiaotong University >

2016 , Vol. 50 >Issue 7: 1075 - 1081

DOI: https://doi.org/10.16183/j.cnki.jsjtu.2016.07.016

Minwise Hash动态双重阈值过滤器

  • 袁鑫攀 ,
  • 曹阳 ,
  • 龙军 ,
  • 赵贵虎
Expand
  • 湖南工业大学, 中南大学

Online published: 2025-07-02

Fold

Abstract

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

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

Cite this article

袁鑫攀 , 曹阳 , 龙军 , 赵贵虎 . Minwise Hash动态双重阈值过滤器[J]. Journal of Shanghai Jiaotong University, 2016 , 50(7) : 1075 -1081 . DOI: 10.16183/j.cnki.jsjtu.2016.07.016

Options
Outlines

/

〈 〉