title: Fast and scalable similarity detection
body: <p>I have large postgresql database, containing documents. Every document represented as a row in the table. When new document added to the database I need to check for duplicates. But I can't just use <code>select</code> to find exact match. Two documents can vary slightly and still can be considered as a duplicates, for example if some minor fields are different and all other fields are equal.</p>
  
  <p>I research this problem and find method to solve this problem. It is possible to calculate <code>MinHash</code> signature for every document and construct inverted index, to query similar documents from the database. But I can't understand how to map <code>MinHash</code> to relational database.</p>
  
  <p>As I understand, <code>MinHash</code> signature is a list of N hashes, where N is a number of attributes. Similarity calculated as follows:</p>
  
  <pre><code># Given 2 signatures Sa and Sb containing N hashes.
  # Calculate number of equal hashes Neq.
  number_of_equal_hashes = 0
  for ix in range(0, N):
      if Sa[ix] == Sb[ix]:
          number_of_equal_hashes += 1
  similarity = float(number_of_equal_hashes)/N
  </code></pre>
  
  <p>This is simple if you already have two signatures, the problem is to find all documents (with corresponding signatures) in the database with similarity less or equal some value.</p>
  
  <p>For example, I can create table with multiple columns like this:</p>
  
  <pre><code>| minhash0 | minhash1 | minhash3 | docid |
  </code></pre>
  
  <p>Each <code>minhashX</code> column corresponds to minhash of the one of the document's attribute and <code>docid</code> is a document's identifier.
  I can query similar records this way:</p>
  
  <pre><code>select * from invidx
  where ((case when minhash0=minhash2search0 then 1 else 0 end) +
         (case when minhash1=minhash2search1 then 1 else 0 end) +
         (case when minhash2=minhash2search2 then 1 else 0 end))/N &gt; THRESHOLD
  </code></pre>
  
  <p>where <code>minhash2searchX</code> is minhashes of new document and THRESHOLD is minimal similarity. But this approach require full scan. Is there any method to speedup this algorithm?</p>