Salmon Run: Near Duplicate Detection using MinHashing and Solr

Salmon Run: Near Duplicate Detection using MinHashing and Solr

Recently there was a discussion on detecting near duplicate documents on LinkedIn (login required). Someone suggested using NGrams, which prompted me to suggest using More Like This (MLT) queries on Solr using shingles for terms (the general idea of querying with shingles is explained here).

Turns out that this was a bit naive. For one thing, the Solr ShingleFilter works differently than you would expect. For example, for the phrase "lipstick on a pig", you would expect 3-grams to be the set of tokens {"lipstick on a", "on a pig"}. With Solr's Shinglefilter, for minShingleSize=3, maxShingleSize=3 and outputUnigrams=true, you get {"lipstick|lipstick on a", "on|on a pig"}, ie synonym tokens with the unigram as anchor and the n-gram(s) as synonyms. If you set outputUnigrams=false, no shingles are produced because there is no anchor for the synonym term. Further, since MLT works by matching tokens found by analyzing a query document with tokens found in index documents, the only way to implement my original suggestion would be a custom ShingleFilter.

While I've built custom Solr components in the past, in hindsight I think its generally a bad idea for two reasons. First the Lucene and Solr projects are quite fast moving and APIs get changed frequently. Second, custom extension points are often regarded as "expert" and there is less concern for backward compatibility for these APIs than the user-centric ones. I guess the expectation is that people doing customizations are responsible for being on top of API changes as they occur. Maybe its true in general, but for me its a potential annoyance I have to deal with each time I upgrade.

In any case, I figured out a user-centric approach to do this. Instead of analyzing the content into shingles (n-grams), we decompose the content into shingles at index time and store them in a multi-valued string (no tokenization beyond the shingling) field. When trying to find near duplicates, we search using a boolean query of shingles built from the query document. This returns a ranked list of documents where topmost document has the most shingles matching the shingles of the query document, the next one less so, and so on.

Read full article from Salmon Run: Near Duplicate Detection using MinHashing and Solr