Я исследовал метод с использованием мини-кучи. Для каждой точки мы можем сохранить минимальную кучу размера k, но для большого n (I m таргетинга для n около 100 миллионов) требуется слишком много места. Разумеется, должен быть лучший способ сделать это, используя меньшее пространство и не сильно влияя на временную сложность. Есть ли другая структура данных?Учитывая n точек в двумерной плоскости, мы должны найти k ближайших соседей каждой точки между собой
Эта проблема типична для KD-tree. Такое решение будет иметь линейную сложность, но может быть относительно сложным для реализации (если готовая реализация недоступна)
Альтернативный подход может заключаться в использовании bucketing для уменьшения сложности наивного алгоритма. Идея состоит в том, чтобы разделить плоскость на «ведра», т. Е. Квадраты некоторого размера и поместить точки в ведро, к которому они принадлежат. Ближайшие точки будут от ближайших ковшей. В случае случайных данных это может быть довольно хорошим улучшением, но худший случай все тот же, что и наивный подход.
Я узнаю о KD-Tree. Также подход к балансировке кажется довольно хорошим. Какая структура данных, по вашему мнению, подходит для ее реализации? Я думаю, что первый поиск по графу с краями, представляющими смежность между ведрами (узлами) в 2D-плоскости, был бы неплохим. – nighthowler
Для реализации я предполагаю, что вы можете использовать либо матрицу 2d с ячейкой для каждого ведра, либо хэш-таблицу (или какой-либо другой ассоциативный массив), если вы ожидаете, что большинство ведер будет пустым –
Как большое значение ** n ** влияет на «большое пространство» - размер кучи составляет ** k **? Вы считали https://en.wikipedia.org/wiki/K-d_tree для вашего размера набора данных? – MBo
Я думаю, что meta рассматривает один minheap для каждой точки. Таким образом, была бы полная «n» min-heap с размером 'k', таким образом, занимая пространство« n * k »в целом. –
@SauravSahu Да, я так и думал об этом. – nighthowler