измерения наименьший угол между вектором и разреженной 30k других предопределенных разреженных векторов

Question

У меня есть разреженный вектор, скажем < 0,0, ..., 0,8,3, ...>

Я бы как найти k ближайших векторов из предопределенного набора 30k векторов. Конкретный «ближний» расчет, который я делаю, похож на скалярное умножение, чтобы найти угол между векторами.

Есть ли способ оптимизировать этот процесс (кроме наивного подхода к составлению 30k-расчетов и сохранению лучших результатов k)? Меня интересует оптимизация времени работы, а не mem

Answer 1

Одно из простых решений состоит в том, чтобы предварительно скопировать все углы и сохранить их в таблице поиска (верхняя треугольная матрица). Это будет стоить 30k * 30k/2 = 450m. Это было бы самым быстрым.

Answer 2

Существует, возможно, связанная с этим проблема, которая, как считается, не имеет неочевидных ускорений. Это проблема нахождения пары ортогональных булевых векторов в списке n. При некоторых условиях стоимость может быть неприводимой O (n^2) - см., Например, слайд 4 из http://theory.stanford.edu/~virgi/conclusions-amir.pdf. Если бы он был ниже, мы могли бы сделать SAT значительно быстрее, чем O (2^n), что, как предполагается, является сложным. Это, по крайней мере, означает, что многие люди рассматривают эту проблему и никуда не денутся.