Если вы используете Python, посмотрите здесь для различных индексов высокой яркости. В основном это индексы отжига, что означает (поправьте меня, если я ошибаюсь), они жертвуют некоторой точностью ради значительных улучшений скорости.
Если вы используете Java и / или заинтересованы в Точность 100%, обратите внимание на PhTree , особенно на версию HD (с высокой яркостью). Это многомерный индекс в памяти, который должен быть способен построить индекс в 1M точек примерно за 10 секунд или около того. Он поддерживает различные функции расстояния, репозиторий содержит реализации евклидова и L1 расстояния. Вам может понадобиться машина с большим количеством оперативной памяти, хотя, я предполагаю (не измерено) около 5-10 ГБ на 1М точек?
Насколько я могу сказать, она превосходит KD-Trees и несколько быстрее, чем R * Trees (см. здесь для коллекции индексов). Я не тестировал его, но я предполагаю, что он не может конкурировать с индексами отжига, но в отличие от индексов отжига, он даст 100% правильные результаты. , поэтому добавление одной и той же координаты дважды перезапишет предыдущую запись. Простой способ обойти это - добавить дополнительное измерение с уникальным идентификатором. Это измерение, конечно, должно быть исключено из расчета расстояния.
Отказ от ответственности: я являюсь автором PH-Tree и библиотеки индексов TinSpin.