Каков наиболее эффективный способ хранения набора точек (вложений), чтобы запросы для ближайших точек вычислялись быстро?

Question

Учитывая набор вложений, то есть набор [имя, векторное представление], как его хранить, чтобы запросы к ближайшим точкам вычислялись быстро.Например, учитывая 100 вложений в 2-мерном пространстве, если я запрашиваю структуру данных в 5 ближайших точках к (10,12), он возвращает {[a, (9,11.5)], [b, (12,14)], ...}

Тривиальный подход - вычислить все расстояния, отсортировать и вернуть топ-k точек.В качестве альтернативы можно подумать о сохранении в двумерном массиве блоков / единиц пространства mXn, чтобы охватить диапазон пространства внедрения.Я не думаю, что это расширяемо для более высоких измерений, но я хочу быть исправленным.

Answer 1

Есть стандартные приблизительные библиотеки ближайших соседей, такие как faiss , flann , java-lsh и т. Д. (Которые могут быть либо LSH или Квантование продукта * на основе 1010 *), которое вы можете использовать.

Самое быстрое решение (которое я нашел полезным) - преобразование вектора (скажем, 100 измерений) в длинную переменную (64 бита).) с помощью преобразования Джонсона – Линденштрауса .Затем вы можете использовать сходство Хэмминга (т.е. 64 минус число битов, установленных в a XOR b ), чтобы вычислить сходство между битовыми векторами a и б .Вы можете использовать машинную инструкцию POPCOUNT для этого эффекта (что очень быстро).

В действительности, если вы используете POPCOUNT в C, даже если вы делаетезавершить итерацию по всему набору бинарно преобразованных векторов (длинные переменные по 64 бита), это все равно будет очень быстро.