использовать kd-дерево
К сожалению, в больших измерениях эта структура данных сильно страдает от проклятия размерности , что делает его время поиска сопоставимым с поиском методом грубой силы.
уменьшить количество измерений
Уменьшение размерности - это хороший подход, который предлагает справедливый компромисс между точностью и скоростью. Вы теряете некоторую информацию, когда уменьшаете свои размеры, но получаете некоторую скорость.
Под точностью я имею в виду нахождение точного ближайшего соседа (NN).
Анализ основных компонентов ( PCA ) - это хорошая идея, если вы хотите уменьшить размерное пространство, в котором живут ваши данные.
Есть ли какой-нибудь умный алгоритм или структура данных, чтобы решить это точно в разумные сроки?
Приблизительный поиск ближайшего соседа ( ANNS ), где вы удовлетворены поиском точки, которая может быть не точным ближайшим соседом, а скорее хорошим приближением к нему (то есть четвертой, например, NN для ваш запрос, в то время как вы ищете 1-й NN).
Такой подход стоит вам точности, но значительно повышает производительность. Более того, вероятность нахождения хорошего NN (достаточно близкого к запросу) относительно высока.
Подробнее об ANNS вы можете прочитать во введении к нашему документу kd-GeRaF .
Хорошая идея - объединить ANNS с уменьшением размерности.
Хеширование с учетом локальных особенностей ( LSH ) - современный подход к решению проблемы ближайшего соседа в больших размерах. Основная идея заключается в том, что точки, которые находятся близко друг к другу, хэшируются в одно и то же ведро. Поэтому, когда запрос поступит, он будет хэширован в сегмент, где этот сегмент (и обычно его соседние) содержит хорошие NN-кандидаты).
FALCONN - хорошая реализация C ++, которая фокусируется на сходстве косинусов. Другой хорошей реализацией является наша DOLPHINN , которая является более общей библиотекой.