title: The Inverted Multi-Index
body: <p>I am trying to understand The Inverted Multi-Index, from this <a href="http://sites.skoltech.ru/app/data/uploads/sites/25/2014/12/TPAMI14.pdf" rel="noreferrer">paper</a>, which has also a smaller version <a href="http://www.robots.ox.ac.uk/~vilem/cvpr2012.pdf" rel="noreferrer">here</a>. For that purpose, I constructed a toy example and would like someone to verify or/and share with me his/her opinion(s).</p>
  
  <p>The example:</p>
  
  <pre><code>Assume we have N = 6 points in M = 4 dimensions. We use two blocks to
  create sub-vecrtors. Let the points be these:
  
  p0 = (0, 0, 1, 1)
  p1 = (2, 2, 3, 3)
  p2 = (4, 4, 5, 5)
  p3 = (6, 6, 7, 7)
  p4 = (8, 8, 9, 9)
  p5 = (10, 10, 11, 11) // p5^1 = (10, 10), which is appended in D^1 etc.
  
  _________________________________________________________________________
  
  We run k-means twice, once for D^1 and once for D^2, by requiring 3
  centroids and we get:
  U = { u1 = (1, 1), u2 = (5, 5), u3 = (9, 9) }
  V = { v1 = (2, 2), v2 = (6, 6), v3 = (10, 10) }
  
  Now we have to assign the points to the Wi,j. All we be empty, except:
  
  W1,1 = (u1, v1): p0, p1
  W2,2 = (u2, v2): p2, p3
  W3,3 = (u3, v3): p4, p5
  
  Note: We store the PQ-copressed version with every point ( for example
  instead of storing just p0, store [p0, (u1, v1)] ), which will be used
  during reranking.
  _________________________________________________________________________
  
  Assume T = 4 (which sets L = 2 for the sake of the example) and the query
  is: (5, 5, 0, 0). Posing the query...
  
  
  q^1 VS U
  i   u_α(i) r
  1   u2     0
  2   u1    32 &lt;-- |d1( (5,5), (1,1) )|^2 = (5 - 1)^2 + (5 - 1)^2 = 32
  
  q^2 VS V
  j   v_β(j) s
  1   v1     8
  2   v2    72
  
  Invoke the Multi Sequence Algorithm which will output:
  W2,1 --&gt; [u2 v1] --&gt; empty
  W1,1 --&gt; [u1 v1] --&gt; p0, p1
  W2,2 --&gt; [u2 v2] --&gt; p4, p5
  // stop when the points that lie in the Ws returned so far are &gt;= T
  
  So the candidate list is {p0, p1, p2, p3}
  _________________________________________________________________________
  
  Rerank the candidate list, by computing the distance between the query and
  the PQ-compressed representation (sum the distances of the subvectors).
  </code></pre>
  
  <p>Is it correct, please?</p>