<p>1) You can bypass it, <em>but</em> then you will work in <code>D</code> dimensions, not <code>N</code> as you say. where <code>N &lt;&lt; D</code>. That means that the algorithm has to adapt to <code>D</code> dimensions as well.</p>

<hr>

<p>2) <em>No</em>.</p>

<p>Read <a href="http://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_feature2d/py_sift_intro/py_sift_intro.html" rel="nofollow">SIFT from openCV</a>:</p>

<blockquote>
  <ol start="4">
  <li>Keypoint Descriptor</li>
  </ol>
  
  <p>Now keypoint descriptor is created. A 16x16 neighbourhood around the
  keypoint is taken. It is devided into 16 sub-blocks of 4x4 size. For
  each sub-block, 8 bin orientation histogram is created. So a total of
  128 bin values are available. It is represented as a vector to form
  keypoint descriptor. In addition to this, several measures are taken
  to achieve robustness against illumination changes, rotation etc.</p>
</blockquote>

<p>Here is how I have it in my mind, hope that will be enough:</p>

<p><strong>LSH takes as input a pointset, of <code>n</code> points, where every point lies in <code>d</code> dimensions.</strong></p>

<p>So, a query is a point, in <code>d</code> dimensions and the goal is to find its NN<sup>*</sup>.</p>

<hr>

<ol>
<li><p>Now every point, represents an image descriptor. So, we have <code>n</code> images in our
dataset.</p></li>
<li><p>The query, which is also a point (i.e. a vector with <code>d</code>
coordinates), represents another image descriptor.</p></li>
<li><p>We are seeking to match (i.e. to find the Nearest Neighbor) the
query image descriptor with an image descriptor from our dataset.</p></li>
</ol>

<p>So the conversion you are talking about is applied in a vector, <em>not</em> a matrix.</p>

<hr>

<p><em>Edit</em>:</p>

<p>Moreover, from our <a href="http://arxiv.org/pdf/1603.09596.pdf" rel="nofollow">High-dimensional approximate nearest neighbor: k-d Generalized Randomized Forests</a> paper, see this in the <em>Experiments</em> section:</p>

<blockquote>
  <p>SIFT is a 128-dimensional vector that describes a local image patch by
  histograms of local gradient orientations.</p>
</blockquote>

<hr>

<p>*<sub>or the <a href="https://en.wikipedia.org/wiki/Fixed-radius_near_neighbors" rel="nofollow">Fixed-radius near neighbors</a> problem</sub></p>
Is LSH about transforming vectors to binary vectors for hamming distance?
<p>I read some paper about LSH and I know that is used for solving the approximated k-NN problem. We can divide the algorithm in two parts:</p>

<ol>
<li><p>Given a vector in <code>D</code> dimensions (where <code>D</code> is big) of any value, translate it with a set of <code>N</code> (where <code>N&lt;&lt;D</code>) hash functions to a binary vector in <code>N</code> dimensions.</p></li>
<li><p>Using hamming distance, apply some search technique on the set of given binary codes obtained from phase 1 to find the k-NN.</p></li>
</ol>

<p>The keypoint is that computing the hamming distance for vectors in <code>N</code> dimensions is fast using XOR.</p>

<p>Anyway, I have two questions:</p>

<ol>
<li><p>Point 1. is still necessary if we use a binary descriptor, like ORB? Since ORB's descriptors are already binaries and we use the hamming distance for comparing them, why we should perform the first point?</p></li>
<li><p>How the conversion happens for images described by SIFT? Each SIFT descriptor is 128 bits and each image is described by a set of descriptors. So we have matrix <code>descX128</code> (where <code>desc</code> is the number of descriptors used), while LSH usually accept as input a vector.</p></li>
</ol>