I have a reasonable understanding of the technique to detect similar documents consisting in first computing their minhash signatures (from their shingles, or n-grams), and then use an LSH-based algorithm to cluster them efficiently (i.e. avoid the quadratic complexity which would entail a naive pairwise exhaustive search).

What I'm trying to do is to bridge three different algorithms, which I think are all related to this minhash + LSH framework, but in non-obvious ways:

  1. The algorithm sketched in Section 3.4.3 of Chapter 3 of the book Mining of Massive Datasets (Rajaraman and Ullman), which seems to be the canonical description of minhashing

  2. Ryan Moulton's Simple Simhashing article

  3. Charikar's so-called SimHash algorihm, described in this article

I find this confusing because what I assume is that although [2] uses the term "simhashing", it's actually doing minhashing in a way similar to [1], but with the crucial difference that a cluster can only be represented by a single signature (even tough multiple hash functions might be involved), while two documents have more chances of being similar with [1], because the signatures can collide in multiple "bands". [3] seems like a different beast altogether, in that the signatures are compared in terms of their Hamming distance, and the LSH technique implies multiple sorting of the signatures, instead of banding them. I also saw (somewhere else) that this last technique can incorporate a notion of weighting, which can be used to put more emphasis on certain document parts, and which seems to lack in [1] and [2].

So at last, my two questions:

  • Is there a (satisfying) way in which to bridge those three algorithms?

  • Is there a way to import this notion of weighting from [3] into [1]?


You are right: what your second link describes is really minhashing. As to the questions,

  • If you haven't already, take a look this paper that compares simhashing with minhashing and describes a hybrid algorithm: "First compute all [minhash]-similar pairs. Then filter out those pairs whose [simhash]-similarity falls below a certain threshold."

  • Not directly, but you could design a signature vector such that different parts of it would come from different parts of the document, and then increase the number of signature-forming hash functions that correspond to the part of the document you want to place more emphasis on. Alternatively, if computational time is limiting, instead of adding more hash functions, use bottom-k technique, and simply increase k for the parts that are more important.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.