If the Jaccard Index between \(d_{i}\) and \(d_{j}\) is sufficiently high, it is likely that documents are approximate matches of each other. To efficiently approximate the Jaccard index, MinHash constructs document signatures by sorting each of the \(n\)-grams via a hash function, and then keeping only the \(k\) smallest hashed \(n\)-grams. There are multiple ways to construct estimators of the Jaccard index from these kinds of signatures [24].