关键词: 数据摘要,集合相似性,奇偶性,近似算法

Abstract: Jaccard similarity is one of the most important methods in set similarity computation.When approximately computing the Jaccard similarity of two sets using the b-bits hash function,if there are multiple elements being similar to the input element with similarity up to 1,the b-bits hash function can’t differentiate these elements very well.In order to improve the accuracy of data sketch and the application performance based on set similarity,this paper proposed a set similarity approximation algorithm based on parity of data sketch.After getting the two permutation sets with minwise hash function,we used two n-bits indicator vectors to represent the parity of elements in the permutation set appearing in indicator vectors,and estimated the Jaccard similarity of original sets based on these two parity vectors.We inferred the parity sketch based on both Markov chain and Poisson distribution models,and verified their equivalence.Experiments on Enron dataset show that the proposed parity sketch is more accurate than the b-bits hash function,and performs much better in both applications of duplicate document detection and associate rule mining.

Key words: Data sketch,Set similarity,Parity,Approximation algorithm