Структура данных C ++ для k Поиск ближайшего соседа в измерении D с использованием только облака точек в качестве точек запроса
У меня есть облако точек из N точек в D-мерном пространстве с периодическими граничными условиями, где N может варьироваться от 500 до 10 ^ 8, а D может варьироваться от 1 до 20. Распределение точек сильно варьируется, от полностью однородного до очень сгруппированного все вместе. Для каждой точки в облаке точек мне нужно найти k ближайших соседей к этой точке. Мне также нужно найти, сколько точек существует на расстоянии каждой точки, в частности, максимальное расстояние. Мне не нужно знать, какие точки находятся в радиусе, сколько их, но это было бы хорошим дополнением.
Я пробовал kd-деревья, но они не обрабатывают границы переноса, а для больших деревьев дублирование неосуществимо. Кроме того, это становится медленным в более высоких измерениях.
Я только что натолкнулся на Vantage Point Trees и попробовал какой-то код, но он медленнее, чем kd-tree. Хотя код, который я нашел, использует рекурсивный метод поиска, без пакетной обработки. С одной стороны, он может обрабатывать условия обертки и не требует дублирования.
Я собираюсь посмотреть, смогу ли я выжать еще немного производительности из дерева VP, перейдя к итеративному подходу и посмотрев, смогу ли я выполнить пакетный поиск, но у меня была мысль. Все эти структуры данных работают для поиска ближайших соседей к произвольным точкам запроса, в то время как мои точки запроса ограничены тем, чтобы быть точками в облаке точек. Я полагаю, что это ограничение может предусматривать более производительную структуру (может быть, своего рода навигационная сетка?). Я пытался найти структуры, которые бы справились с этим, но мой гугл-фу меня подводит. Так что просто интересно, если кто-нибудь знает о структуре данных, которая может обрабатывать следующее:
- Обработка небольшого и большого количества баллов, т.е. 500-10 ^ 8 баллов
- Обрабатывать до 20 размеров
- Работа с периодическими границами (т. Е. Плоский тор)
- Работа с максимальным расстоянием (мягкое требование. Евклидов может дать мне потенциальный список, который я могу выбрать вручную, но предпочтительнее maxnorm)
- Можно найти k-NN для точки запроса, а также узнать, сколько точек существует с расстоянием до точки запроса
- Точки запроса — это только точки в структуре, а не произвольные точки
- Запросы могут быть пакетными. Т.е. мне нужно найти k-е NN для каждой точки в облаке точек. Мне также нужно найти, сколько точек существует в пределах d [i] для каждой точки i. То есть каждая точка имеет разный радиус поиска.
- Не нуждается в поддержке вставки или удаления.
Спасибо
Решение
Я сомневаюсь, что есть полный и определенный ответ на вашу очень сложную проблему, поэтому я просто делюсь своими мыслями.
Ваша спецификация проблемы сочетает в себе ряд вещей, которые плохо работают вместе (высокая размерность, неевклидова метрика, совершенно разные типы запросов). Если алгоритм должен принять общий случай, он обязательно медленный.
Давайте сначала разберемся со специальными случаями, когда известны хорошие структуры данных.
- Если ваше измерение равно 1, используйте отсортированную карту.
- Если ваше измерение 2-3 (возможно, даже 4), сортированные поиски и географические базы данных должны быть оптимальными.
https://en.wikipedia.org/wiki/R-tree - Если ваши точки имеют более высокое измерение, но очень сильную корреляцию, уменьшение размерности может сопоставить ваше облако точек с тем, которое имеет такое низкое измерение, и уменьшить проблему до простого.
https://en.wikipedia.org/wiki/Dimensionality_reduction - Если ваше количество очков меньше 10 ^ 6, грубая сила самая дешевая. Просто рассчитайте расстояние с помощью вашей метрики для всех точек, а затем выполните частичную сортировку для k результатов. Эти простые когерентные вычисления выполняются быстрее, чем использование древовидных структур.
http://en.cppreference.com/w/cpp/algorithm/partial_sort - Если ваш k ограничен, скажем, к <= 20, и вы оптимизируете время запроса, предварительно рассчитав таблицу со всеми результатами.
- Если только некоторые из ваших измерений являются периодическими, я думаю, что вы должны адаптировать алгоритм kd-tree для их обработки (добавляя более сложные узлы сравнения для этих измерений, аналогичных тем, что в деревьях точек обзора).
Если все это не относится (если вы имеете в виду практическое применение, пожалуйста, поделитесь с нами), ваш случай очень общий.
В дополнение к алгоритмам, которые вы упомянули, вы должны также попробовать геометрические деревья доступа к ближнему соседству (GNAT).
http://infolab.stanford.edu/~sergey/near.html
Они применяются к общим метрикам (включая вашу), а также обрабатывают неравномерное распределение.
Кроме того, я думаю, что ваши ожидания очень высоки. Вы можете сравнить с хорошей реализацией дерева kd (например, https://github.com/mariusmuja/flann), которая решает проблему только с евклидовой метрикой. Если это занимает много времени, не стоит ожидать, что более общие метрики будут решаться быстрее.
Следует признать, что более общий метод не может использовать ваше ограничение, что запросы являются точками в облаке. Мне было бы очень интересно, есть ли такое решение.
Другие решения
Если вариант Java (производительность похожа на C ++ в настоящее время), посмотрите на ELKI библиотека. Он обеспечивает реализации многочисленных многомерных индексов, включая подходы к уменьшению размерности и заполнению кривых. Он также предоставляет множество алгоритмов для kNN (евклидовых / неевклидных), обнаружения кластеров, запросов диапазона и т. Д. (Обычно вы можете определить свой собственный фильтр запросов с пользовательской метрикой расстояния).
Для КНН я могу специально рекомендовать CoverTree и (немного медленнее, но более общего назначения) PH-Tree, Я тестировал оба до 27 размеров. Дерево PH особенно подходит для кластеризованных и больших наборов данных (я протестировал более 100 000 000 точек). (Отказ от ответственности: PH-Tree основан на моих собственных исследованиях, но я думаю, что ваш вариант использования отлично подходит.)
Однако, насколько мне известно, ни один из этих подходов не обеспечивает особой оптимизации, как вы предложили.