Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Could kd-tree build with dot-product?

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?

like image 985
xunzhang Avatar asked Sep 01 '25 09:09

xunzhang


1 Answers

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

like image 57
Andy Jones Avatar answered Sep 03 '25 21:09

Andy Jones