title: Fast k-NN search over bag-of-words models
body: <p>I have a large amount of documents of equal size. For each of those documents I'm building a bag of words model (BOW). Number of possible words in all documents is limited and large (2^16 for example). Generally speaking, I have N histograms of size K, where N is a number of documents and K is histogram width. I can calculate distance between any two histograms.</p>
  
  <p><strong>First optimization opportunity.</strong> Documents usually uses only small subset of words (usually less then 5%, most of them less then 0.5%).</p>
  
  <p><strong>Second optimization opportunity</strong> Subset of used words is varying from document to document much so I can use bits instead of word counts.</p>
  
  <h3>Query by content</h3>
  
  <p>Query is a document as well. I need to find <code>k</code> most similar documents.</p>
  
  <h3>Naive approach</h3>
  
  <ul>
  <li>Calculate BOW model from query.</li>
  <li>For each document in dataset:
  
  <ul>
  <li>Calculate it's BOW model.</li>
  <li>Find distance between query and document.</li>
  </ul></li>
  </ul>
  
  <p>Obviously, some data structure should be used to track top-ranked documents (priority queue for example).</p>
  
  <p>I need some sort of index to get rid of full database scan. KD-tree comes to mind but dimensionality and size of the dataset is very high. One can suggest to use some subset of possible words as features but I don't have separate training phase and can't extract this features beforehand.</p>
  
  <p>I've thought about using MinHash algorithm to prune search space but I can't design an appropriate hash functions for this task.</p>