Dynamic double-threshold filter for minwise hash

作者：Yuan Xinpan; Cao Yang; Long Jun^*; Zhao Guihu

来源：Journal of Shanghai Jiaotong University, 2016, 50(7): 1075-1081.

DOI：10.16183/j.cnki.jsjtu.2016.07.016

• Binomial distribution
• Double threshold
• Dynamic threshold
• Hash
• Mutation algorithms
• Similarity detection
• Small probability events
• Small probability principle

By combining the binomial distribution with the small probability principle, a dynamic double-threshold filter for Minwise Hash was proposed. The filter divides compared progress into several compared point and sets dynamic threshold on them to filter documents with similarity under lower threshold TL(k) and output documents with similarity exceed upper threshold TU(k). It decreases the comparing time and workload that follow. The experimental results demonstrate that the dynamic double-threshold filter requires only 31% of CPU running time of Minwise Hash or 36% of b-bit Minwise Hash. Besides, the performance of the filter is enhanced with a set of suitable parameters. The filter applies not only to Minwise Hash, but also to its mutation algorithm (e.g. b-bit Minwise Hash), and even all estimators conforming to binomial distribution.

• 出版日期2016
• 单位中南大学