A second look at Broder's MinHash without alignment

We study Broder's MinHash estimator for Jaccard similarity of two sets without assuming alignment under random permutations. Broder's estimator uses the proportion of permutations for which the minimum permuted values M_1 and M_2 of the two sets are equal. Li and K"onig previously used these events to construct a maximum likelihood estimator. We construct alternative estimators that also use the non-alignment events M_1 > M_2 and M_1 < M_2. We derive their asymptotic bias and variance, showing that these additional events can give lower asymptotic variance compared with Broder's MinHash, with the improvement depending on the estimator and set sizes. Experiments validate the asymptotic expressions and show lower empirical mean squared error (MSE). Our work shows that non-alignment events contain useful information that is discarded by the standard MinHash estimator.