Нахождение 10 ближайших точек в трехмерном евклидовом пространстве для КАЖДОГО элемента в каталоге с 5 миллионами элементов

Question

Предположим, у меня есть каталог из 5 миллионов точек с их координатами x,y,z в трехмерном пространстве. Для КАЖДОГО из этих 5 миллионов точек я хочу найти 10 ближайших к нему точек (простая трехмерная евклидова формула расстояния).

В Python, если я делаю простой цикл for для каждого элемента в таблице, а внутри цикла for выполняю операцию массива (не секунды для цикла!), Чтобы найти расстояние между текущей точкой и всеми другими точками в каталоге, это займет дни / недели. Я пробовал некоторые вещи, включающие сортировку и вычисление расстояния между точками только +/- пару тысяч строк вокруг каждого элемента таблицы, но это все равно займет дни.

Какой более быстрый способ сделать это в Python? Есть ли способ превратить цикл for в некую векторизованную операцию? Будут ли полезны какие-либо методы машинного обучения (например, в scikit-learn)? Или поможет распараллеливание кода?

Answer 1

Я использовал пакет под названием RANN в R, который находит "приблизительных" ближайших соседей. Я запустил его за несколько минут с 25 М наблюдениями и 8 измерениями, и результаты были достаточно хороши для моего случая использования.

Я не уверен, что есть версия Python пакета, который я использовал, но я нашел эту ссылку, которая имеет много альтернатив: Тест ANN Libraries

Контрольный показатель библиотек ANN