title: Query points on the vertices of a Hamming cube
body: <p>I have N points that lie only on the vertices of a cube, of dimension D, where D is something like 3.</p>
  
  <p>A vertex may not contain any point. So every point has coordinates in {0, 1}<sup>D</sup>. I am only interested in <em>query time</em>, as long as the memory cost is reasonable ( not exponential in N for example :) ).</p>
  
  <p>Given a query that lies on one of the cube's vertices and an input parameter <code>r</code>, find all the vertices (thus points) that have <em>hamming distance</em> &lt;= <code>r</code> with the query.</p>
  
  <p>What's the way to go in a <a href="/questions/tagged/c%2b%2b" class="post-tag" title="show questions tagged &#39;c++&#39;" rel="tag">c++</a> environment?</p>
  
  <hr>
  
  <p>I am thinking of a kd-tree, but I am not sure and want help, any input, even approximative, would be appreciated! Since <em>hamming distance</em> comes into play, bitwise manipulations should help (e.g. XOR).</p>