<p>I think <a href="http://arxiv.org/pdf/1202.6101.pdf" rel="nofollow">Ram &amp; Gray 2008</a> is exactly what you're looking for. They call their structure a "cone tree".</p>
Could kd-tree build with dot-product?
<p>A normal kd-tree is constructed by recursively split the super plane into half. And to do range search with a query point, it will only search a small bunch of points(log) in stead of all(linear).</p>

<p>I wonder a kd-tree can be built with dot product?</p>

<p>For example, b is a list of 3d vector:</p>

<pre><code>b = np.random.rand(10,3)

a = (1,1,1) is a query vector
</code></pre>

<p>and I want to find nearest bk which satisfy:</p>

<pre><code>a * bk &gt; a * bi, for i = 1, 2, ...k-1, k+1, 10
</code></pre>

<p>I do not want to calculate all a * bi dot product pairs.</p>

<p>How can I build a tree with b, and when query a come, I only calculate some of a * bi?</p>