Я получил N-мерное пространство с миллионами точек. Я ищу наиболее эффективный способ построить модель, которая позволила бы найти K (K‹100) точек, ближайших к заданной точке во время выполнения.
Список FindClosestMatch (точечная цель, модель модели)
Я начинаю смотреть на R*-деревья, но думаю, правильный ли это подход...
Варианты R-Tree — довольно хороший выбор, но M-деревья немного лучше подходят для вашего приложения, поскольку вам нужно вычислить только одно расстояние, чтобы определить, насколько близко ограничивающая сфера находится к вашей целевой точке:
https://en.wikipedia.org/wiki/M-tree
Вы можете разделить свое пространство на n-кубов так, чтобы ожидаемое количество точек в кубе было равно rk для некоторого значения r > 1, которое необходимо определить. Тогда для заданного запроса p:
1. Consider the 3^n n-cubes at most 1 away from the cube p is in.
2. Calculate the shortest distance d between p and one of these cubes.
3. Find the distance between p and each point in these cubes.
4. If the total number of points within d is >= k, return the k closest.
5. If not, expand your radius by one cube and repeat.
Когда вы выбираете r, вы жертвуете наличием большего набора точек по умолчанию для поиска, вместо того, чтобы увеличивать радиус в 1 или более раз.
Вы также можете просмотреть деревья обложек, которые специально предназначены для поиска kNN. Я также обнаружил, что PH-дерево (мое собственное) работает почти так же хорошо, как и дерево покрытия для 15 или 25 измерений. , при этом значительно экономя место в памяти, особенно для больших наборов данных, и обеспечивая быструю вставку/обновление.
Сравнительная Java-реализация многих алгоритмов доступна в ELKI Framework.
