У меня есть набор данных с миллионами точек в 100-мерном пространстве. Мне нужно быстро проверить, является ли точка запроса , а не в пределах определенного расстояния до любой из точек в наборе.
Существуют ли быстрые алгоритмы для него?
Алгоритм может иметь ложные срабатывания (скажем, запрос близок к другой точке), но не должен иметь ложных отрицаний (скажем, запрос далек от каждого точка, когда это не так).
Сложность здесь:
Количество измерений проклято . Это огромное пространство, но все относительно близко друг к другу.
Большинство алгоритмов KNN сосредоточены на поиске лучшего кандидата и отбрасывании всех точек дальше, чем лучший кандидат. В моем случае почти каждый запрос является «пропущенным», поэтому лучший кандидат всегда слишком далеко, чтобы отклонить даже половину баллов.