Сравнение времени выполнения запросов Nearest Neighbor для разных структур данных
Для n точек в d-мерном пространстве существует несколько структур данных, таких как Kd-Trees, Quadtrees и т. Д. Для индексации точек. На этих структурах данных можно реализовать прямой алгоритм для запросов ближайшего соседа вокруг заданной входной точки. Существует ли книга, статья, опрос..., в которой сравнивается теоретическая (в основном ожидаемая) среда выполнения запроса ближайшего соседа для разных структур данных? Данные, на которые я смотрю, состоят из довольно маленьких облаков точек, поэтому все они могут быть обработаны в основной памяти. Для простоты я предполагаю, что данные распределены равномерно. То есть меня не интересуют реальные результаты, а скорее теоретические результаты
2 ответа
Вы позволяете измерению точек не определяться, и вы просто даете приближение для количества точек. Что значит маленький? Относительно того, что один человек имеет в виду под маленьким.
То, что вы ищете, конечно, не существует. Ваш вопрос в значительной степени такой:
Вопрос:
Какова оптимальная структура данных для небольшого (что для вас значит маленький) набора данных любого измерения с данными, которые следуют за равномерным распределением?
Ответ:
Там нет такой структуры данных.
Разве не было бы слишком странно иметь ответ на этот вопрос? Ложная аналогия была бы в качестве синонима этого вопроса: "Какой язык программирования является оптимальным?". Вопрос, который есть у большинства студентов первого курса. Ваш вопрос не настолько наивен, но он идет по тому же пути.
Почему нет такой структуры данных?
Потому что размер набора данных является переменным. Это означает, что у вас может быть набор данных в 2 измерениях, но это также может означать, что у вас есть набор данных в 1000 измерениях, или даже лучше, набор данных в 1000 измерениях с внутренним измерением, которое намного меньше 1000. Подумайте об этом. Можно ли предложить структуру данных, которая будет вести себя одинаково хорошо для трех наборов данных, которые я упомянул? Я сомневаюсь.
На самом деле, есть некоторые структуры данных, которые действительно хорошо ведут себя в низких измерениях (например, квадродерево и KD-деревья), в то время как другие работают намного лучше в более высоких измерениях (например, лес RKD-дерева).
Более того, алгоритмы и ожидания, используемые для поиска ближайших соседей, сильно зависят от размера набора данных (а также от размера набора данных и характера запросов (например, запроса, который находится слишком далеко от набора данных или равноудаленного). из точек набора данных, вероятно, приведет к снижению производительности поиска)).
В более низких измерениях можно выполнить поиск k-ближайшего соседа (k-NN). В более высоких измерениях было бы более разумно выполнить k-Приближенный поиск NN. В этом случае мы следуем следующему компромиссу:
Скорость против точности
Что происходит, так это то, что мы достигаем более быстрого выполнения программы, жертвуя правильностью нашего результата. Другими словами, наша процедура поиска будет относительно быстрой, но она может (вероятность этого зависит от многих параметров, таких как характер вашей проблемы и используемая вами библиотека) не возвращать истинное значение NN, а приближать точный NN. Например, он может не найти точное NN, но третье NN к точке запроса. Вы также можете проверить приблизительный-nn-поисковый вики-тег.
Почему бы не всегда искать точный NN? Из-за проклятия размерности, что приводит к тому, что решения, представленные в более низких измерениях, ведут себя так же хорошо, как и грубая сила (ищите все точки в наборе данных для каждого запроса).
Вы видите, мой ответ уже стал большим, поэтому я должен остановиться здесь. Ваш вопрос слишком широкий, но интересный, я должен признать.:)
В заключение, какая структура данных (и алгоритм) будет оптимальной для использования, зависит от вашей проблемы. Размер набора данных, с которым вы работаете, измерение и внутреннее измерение точек играют ключевую роль. Количество и характер запросов также играют важную роль.
Для поиска ближайших соседей потенциально неоднородных точечных данных я думаю, что kd-дерево даст вам лучшую производительность в целом. Что касается широких обзоров и теоретического анализа затрат, я думаю, что Wikipedia - хорошее место для начала, но имейте в виду, что она не охватывает большую часть реальной оптимизации:
http://en.wikipedia.org/wiki/Nearest_neighbor_search
http://en.wikipedia.org/wiki/Space_partitioning
Теоретическая производительность - это одно, а реальная производительность - совсем другое. Реальная производительность зависит как от деталей реализации структуры данных, так и от типа структуры данных. Например, реализация без указателя (компактный массив) может быть во много раз быстрее, чем реализация на основе указателя из-за улучшенной согласованности кэша и более быстрого выделения данных. Более широкое ветвление может быть медленнее в теории, но быстрее на практике, если вы используете SIMD для тестирования нескольких ветвей одновременно.
Также точная природа ваших точечных данных может оказать большое влияние на производительность. Равномерное распределение менее требовательно и может быть быстро обработано с помощью более простых структур данных. Неравномерное распределение требует большей осторожности. (Kd-деревья хорошо работают как для однородных, так и для неоднородных данных.) Кроме того, если ваши данные слишком велики для обработки в ядре, вам нужно будет использовать совершенно иной подход по сравнению с меньшими наборами данных.