Можно ли построить kd-дерево с помощью dot-product?

Question

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

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

Например, b - это список 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

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

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

Answer 1

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