Не удалось построить kd-tree с dot-продуктом?

Question

Нормальное kd-дерево построено путем рекурсивного разбиения суперплоскости на половину. И для поиска диапазона с помощью точки запроса он будет искать только небольшую группу точек (log) вместо всех (линейных).

Интересно, можно ли построить kd-дерево с помощью точечного продукта?

Например, б приведен список 3d вектора:

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

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

и я хочу, чтобы найти ближайший Б.К., которые удовлетворяют:

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

Я не хочу, чтобы вычислить все на * би точку пар продуктов.

Как я могу построить дерево с b, и когда запрос пришел, я только вычислил некоторые из * би?

Answer 1

Я думаю, Ram & Gray 2008 - это именно то, что вы ищете. Они называют их структуру «конусным деревом».