Could kd-tree build with dot-product?

Question

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).

I wonder a kd-tree can be built with dot product?

For example, b is a list of 3d vector:

b = np.random.rand(10,3)

a = (1,1,1) is a query vector

and I want to find nearest bk which satisfy:

a * bk > a * bi, for i = 1, 2, ...k-1, k+1, 10

I do not want to calculate all a * bi dot product pairs.

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

Answer 1

I think Ram & Gray 2008 is exactly what you're looking for. They call their structure a "cone tree".