Поиск ближайшего соседа

Поиск ближайшего соседа ( NNS ), как форма поиска близости , представляет собой задачу оптимизации поиска точки в заданном наборе, которая является ближайшей (или наиболее похожей) к данной точке. Близость обычно выражается через функцию несходства: чем менее похожи объекты, тем больше значения функции.

Формально задача поиска ближайшего соседа (NN) определяется следующим образом: учитывая набор S точек в пространстве M и точку запроса q ∈ M , найдите ближайшую точку в S к q . Дональд Кнут в об. 3 книги «Искусство компьютерного программирования» (1973) назвал это проблемой почтового отделения , имея в виду применение привязки к месту жительства ближайшего почтового отделения. Прямым обобщением этой проблемы является поиск k -NN, где нам нужно найти k ближайших точек.

Чаще всего M является метрическим пространством , и несходство выражается как метрика расстояния , которая является симметричной и удовлетворяет неравенству треугольника . Еще более распространено, что M считается d -мерным векторным пространством , где несходство измеряется с использованием евклидова расстояния , манхэттенского расстояния или другой метрики расстояния . Однако функция несходства может быть произвольной. Одним из примеров является асимметричная дивергенция Брегмана , для которой неравенство треугольника не выполняется. ^[1]

Приложения

Задача поиска ближайшего соседа возникает во многих областях применения, в том числе:

Распознавание образов – в частности, для оптического распознавания символов
Статистическая классификация - см. Алгоритм k-ближайшего соседа.
Компьютерное зрение – для регистрации облаков точек ^[2]
Вычислительная геометрия - см. Задача о ближайшей паре точек.
Криптоанализ - для задачи решетки ^[3]
Базы данных – например, поиск изображений на основе контента.
Теория кодирования - см. Декодирование максимального правдоподобия.
Семантический поиск
Сжатие данных – см. MPEG-2. стандарт
Роботизированное зондирование ^[4]
Системы рекомендаций , например, см. Совместную фильтрацию.
Интернет-маркетинг – см. контекстную рекламу и поведенческий таргетинг.
секвенирование ДНК
Проверка орфографии – подсказка правильного написания
Обнаружение плагиата
Оценки сходства для прогнозирования карьерного пути профессиональных спортсменов.
Кластерный анализ - распределение набора наблюдений на подмножества (называемые кластерами), так что наблюдения в одном кластере в некотором смысле похожи, обычно на основе евклидова расстояния.
Химическое сходство
Планирование движения на основе выборки

Методы

Были предложены различные решения проблемы ННС. Качество и полезность алгоритмов определяются временной сложностью запросов, а также пространственной сложностью любых структур поисковых данных, которые необходимо поддерживать. Неформальное наблюдение, обычно называемое проклятием размерности, гласит, что не существует точного решения общего назначения для NNS в многомерном евклидовом пространстве с использованием полиномиальной предварительной обработки и полилогарифмического времени поиска.

Точные методы

Линейный поиск

Самое простое решение проблемы NNS — вычислить расстояние от точки запроса до любой другой точки в базе данных, отслеживая «лучшее на данный момент». алгоритм, иногда называемый наивным подходом, имеет работы время O ( dN ), где N — мощность S S. а d — размерность Этот , Нет никаких структур данных поиска, которые нужно поддерживать, поэтому линейный поиск не требует пространственной сложности, кроме хранения базы данных. Наивный поиск в среднем может превосходить подходы к разбиению пространства в пространствах более высокой размерности. ^[5]

Для сравнения расстояний не требуется абсолютное расстояние, а только относительное расстояние. В геометрических системах координат расчет расстояния можно значительно ускорить, исключив вычисление квадратного корня из расчета расстояния между двумя координатами. Сравнение расстояний все равно даст идентичные результаты.

Разделение пространства

С 1970-х годов ветвей и границ к этой проблеме применяется методология . В случае евклидова пространства этот подход включает методы пространственного индекса или пространственного доступа. несколько методов разделения пространства Для решения проблемы NNS было разработано . Пожалуй, самым простым является дерево kd , которое итеративно делит пространство поиска пополам на две области, содержащие половину точек родительской области. Запросы выполняются путем обхода дерева от корня к листу путем оценки точки запроса при каждом разбиении. В зависимости от расстояния, указанного в запросе, может также потребоваться оценка соседних ветвей, которые могут содержать совпадения. Для времени запроса постоянного измерения средняя сложность равна O (log N ). ^[6] в случае случайно распределенных точек сложность в худшем случае равна O ( kN ^(1-1/ k )) ^[7] В качестве альтернативы структура данных R-дерева была разработана для поддержки поиска ближайшего соседа в динамическом контексте, поскольку она имеет эффективные алгоритмы вставки и удаления, такие как дерево R* . ^[8] R-деревья могут давать ближайших соседей не только для евклидова расстояния, но также могут использоваться с другими расстояниями.

В случае общего метрического пространства подход ветвей и границ известен как подход метрического дерева . Конкретные примеры включают методы vp-дерева и BK-дерева .

Используя набор точек, взятых из трехмерного пространства и помещенных в дерево BSP , и учитывая точку запроса, взятую из того же пространства, дается возможное решение проблемы поиска ближайшей точки облака точек к точке запроса. в следующем описании алгоритма.

(Строго говоря, такой точки не может существовать, поскольку она не может быть уникальной. Но на практике обычно нас интересует только поиск какой-либо одной из подмножеств всех точек облака точек, которые существуют на кратчайшем расстоянии от заданной точки запроса. ) Идея состоит в том, чтобы для каждого ветвления дерева предположить, что ближайшая точка в облаке находится в полупространстве, содержащем точку запроса. Возможно, это не так, но это хорошая эвристика. Рекурсивно пройдя все хлопоты по решению задачи для угаданного полупространства, теперь сравните расстояние, возвращаемое этим результатом, с кратчайшим расстоянием от точки запроса до плоскости разбиения. Это последнее расстояние представляет собой расстояние между точкой запроса и ближайшей возможной точкой, которая может существовать в необыскиваемом полупространстве. Если это расстояние больше, чем полученное в предыдущем результате, то очевидно, что нет необходимости искать другое полупространство. Если есть такая необходимость, то вы должны решить задачу для другого полупространства, а затем сравнить ее результат с предыдущим результатом и затем вернуть правильный результат. Производительность этого алгоритма ближе к логарифмическому времени, чем к линейному времени, когда точка запроса находится рядом с облаком, поскольку, когда расстояние между точкой запроса и ближайшей точкой облака точек приближается к нулю, алгоритму нужно только выполнить поиск, используя точка запроса как ключ для получения правильного результата.

Методы аппроксимации

Алгоритму приблизительного поиска ближайшего соседа разрешено возвращать точки, расстояние которых от запроса не превышает $c$ умноженное на расстояние от запроса до ближайших точек. Привлекательность этого подхода заключается в том, что во многих случаях приблизительный ближайший сосед почти так же хорош, как и точный. В частности, если измерение расстояния точно отражает понятие качества пользователя, то небольшие различия в расстоянии не должны иметь значения. ^[9]

Жадный поиск в графах окрестностей близости

Методы графов близости (например, навигационные графы маленького мира). ^[10] и HNSW ^[11]^[12]) считаются современным средством приблизительного поиска ближайших соседей.

Методы основаны на жадном обходе графов окрестностей. $G(V,E)$ в котором каждая точка $x_{i}\in S$ однозначно связан с вершиной $v_{i}\in V$ . Поиск ближайших соседей запроса q в множестве S принимает форму поиска вершины в графе $G(V,E)$ . Базовый алгоритм – жадный поиск – работает следующим образом: поиск начинается с вершины точки входа. $v_{i}\in V$ вычисляя расстояния от запроса q до каждой вершины его окрестности $\{v_{j}:(v_{i},v_{j})\in E\}$ , а затем находит вершину с минимальным значением расстояния. Если значение расстояния между запросом и выбранной вершиной меньше, чем между запросом и текущим элементом, то алгоритм перемещается к выбранной вершине, и она становится новой точкой входа. Алгоритм останавливается, когда достигает локального минимума: вершины, в окрестности которой нет вершины, которая находится ближе к запросу, чем сама вершина.

Идея графов окрестностей близости использовалась во многих публикациях, включая основополагающую статью Арьи и Маунта: ^[13] в системе ВороНет для самолета, ^[14] в системе RayNet для $\mathbb {E} ^{n}$ , ^[15] и в Судоходном Малом Мире, ^[10] Метризованный маленький мир ^[16] и HNSW ^[11]^[12] алгоритмы для общего случая пространств с функцией расстояния. Этим работам предшествовала новаторская работа Туссена, в которой он ввел понятие графа относительной окрестности . ^[17]

Хеширование с учетом местоположения

Хэширование с учетом местоположения (LSH) — это метод группировки точек в пространстве в «корзины» на основе некоторой метрики расстояния, действующей на точки. Точки, близкие друг к другу по выбранной метрике, с высокой вероятностью сопоставляются с одним и тем же сегментом. ^[18]

Поиск ближайших соседей в пространствах с малой внутренней размерностью

Дерево покрытия имеет теоретическую границу, основанную на константе удвоения набора данных . Ограничение времени поиска составляет O ( c ¹² log n ), где c — константа расширения набора данных.

Прогнозируемый радиальный поиск

В особом случае, когда данные представляют собой плотную трехмерную карту геометрических точек, проекционная геометрия метода зондирования может использоваться для значительного упрощения задачи поиска. Этот подход требует, чтобы трехмерные данные были организованы посредством проекции на двумерную сетку, и предполагает, что данные пространственно гладкие в соседних ячейках сетки, за исключением границ объекта. Эти предположения справедливы при работе с данными 3D-датчиков в таких приложениях, как геодезия, робототехника и стереозрение, но могут не соответствовать неорганизованным данным в целом. На практике этот метод имеет среднее время поиска O ( 1 ) или O ( K ) для задачи k -ближайшего соседа при применении к реальным данным стереовидения. ^[4]

Файлы векторной аппроксимации

В многомерных пространствах древовидные структуры индексации становятся бесполезными, поскольку в любом случае необходимо исследовать все больший процент узлов. Чтобы ускорить линейный поиск, сжатая версия векторов признаков, хранящихся в оперативной памяти, используется для предварительной фильтрации наборов данных при первом запуске. Окончательные кандидаты определяются на втором этапе с использованием несжатых данных с диска для расчета расстояния. ^[19]

Поиск на основе сжатия/кластеризации

Подход VA-файла представляет собой особый случай поиска на основе сжатия, при котором каждый компонент объекта сжимается равномерно и независимо. Оптимальным методом сжатия в многомерных пространствах является векторное квантование (VQ), реализуемое посредством кластеризации. База данных кластеризуется и извлекаются наиболее «многообещающие» кластеры. Наблюдались огромные преимущества по сравнению с VA-File, древовидными индексами и последовательным сканированием. ^[20]^[21] Также обратите внимание на параллели между кластеризацией и LSH.

Варианты

Существует множество вариантов задачи NNS, и два наиболее известных — это поиск k -ближайшего соседа и поиск ε-приблизительного ближайшего соседа .

k - ближайшие соседи

Поиск k -ближайшего соседа верхних идентифицирует k ближайших соседей к запросу. Этот метод обычно используется в прогнозной аналитике для оценки или классификации точки на основе консенсуса ее соседей. Графы k -ближайших соседей — это графы, в которых каждая точка соединена со своими k ближайшими соседями.

Примерный ближайший сосед

В некоторых приложениях может быть приемлемо получить «верное предположение» о ближайшем соседе. В таких случаях мы можем использовать алгоритм, который не гарантирует возврат фактического ближайшего соседа в каждом случае в обмен на повышение скорости или экономию памяти. Часто такой алгоритм в большинстве случаев находит ближайшего соседа, но это сильно зависит от запрашиваемого набора данных.

Алгоритмы, поддерживающие приблизительный поиск ближайшего соседа, включают хеширование с учетом местоположения , поиск по принципу «сначала лучший бин» и поиск на основе дерева сбалансированного разложения блоков . ^[22]

Соотношение расстояний до ближайшего соседа

Коэффициент расстояния до ближайшего соседа применяет пороговое значение не к прямому расстоянию от исходной точки до соседа-претендента, а к его отношению, зависящему от расстояния до предыдущего соседа. Он используется в CBIR для получения изображений посредством «запроса по примеру», используя сходство между местными объектами. В более общем смысле это связано с несколькими задачами сопоставления .

Фиксированный радиус рядом с соседями

Фиксированный радиус вблизи соседей — это проблема, когда нужно эффективно найти все точки, заданные в евклидовом пространстве, на заданном фиксированном расстоянии от указанной точки. Предполагается, что расстояние фиксировано, но точка запроса является произвольной.

Все ближайшие соседи

Для некоторых приложений (например, оценка энтропии ) мы можем иметь N точек данных и хотим знать, кто является ближайшим соседом для каждой из этих N точек . Конечно, этого можно было бы достичь, запустив поиск ближайшего соседа один раз для каждой точки, но улучшенной стратегией был бы алгоритм, который использует избыточность информации между этими N запросами для обеспечения более эффективного поиска. Простой пример: когда мы находим расстояние от точки X до точки Y , это также сообщает нам расстояние от точки Y до точки X , поэтому одно и то же вычисление можно повторно использовать в двух разных запросах.

Учитывая фиксированную размерность, полуопределенная положительная норма (тем самым включая все L ^п норма ) и n точек в этом пространстве, ближайший сосед каждой точки может быть найден за время O ( n log n ), а m ближайших соседей каждой точки могут быть найдены за время O ( mn log n ). ^[23]^[24]

См. также

Ссылки

Цитаты

^ Кейтон, Лоуэренс (2008). «Быстрый поиск ближайшего соседа для расхождений Брегмана». Материалы 25-й Международной конференции по машинному обучению . стр. 112–119. дои : 10.1145/1390156.1390171 . ISBN 9781605582054 . S2CID 12169321 .
^ Цю, Дэюань, Стефан Мэй и Андреас Нюхтер. «Поиск ближайшего соседа с ускорением на графическом процессоре для 3D-регистрации». Международная конференция по системам компьютерного зрения. Шпрингер, Берлин, Гейдельберг, 2009 г.
^ Беккер, Дукас, Гама и Лаарховен. «Новые направления поиска ближайших соседей с применением решетчатого просеивания». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (стр. 10–24). Общество промышленной и прикладной математики.
^ Jump up to: ^а ^б Бьюли, А.; Апкрофт, Б. (2013). Преимущества использования структуры проекции для сегментации плотных трехмерных облаков точек (PDF) . Австралийская конференция по робототехнике и автоматизации.
^ Вебер, Роджер; Шек, Ханс-Дж.; Блотт, Стивен (1998). «Количественный анализ и исследование эффективности методов поиска по сходству в пространствах большой размерности» (PDF) . VLDB '98 Материалы 24-й Международной конференции по очень большим базам данных . стр. 194–205.
^ Эндрю Мур. «Вводное руководство по деревьям KD» (PDF) . Архивировано из оригинала (PDF) 3 марта 2016 г. Проверено 3 октября 2008 г.
^ Ли, DT ; Вонг, СК (1977). «Анализ наихудшего случая для поиска областей и частичных областей в многомерных двоичных деревьях поиска и сбалансированных квадродеревьях». Акта Информатика . 9 (1): 23–29. дои : 10.1007/BF00263763 . S2CID 36580055 .
^ Руссопулос, Н.; Келли, С.; Винсент, Рузвельт (1995). «Запросы ближайших соседей». Материалы международной конференции ACM SIGMOD 1995 года по управлению данными – SIGMOD '95 . п. 71. дои : 10.1145/223784.223794 . ISBN 0897917316 .
^ Андони, А.; Индик, П. (01 октября 2006 г.). «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерностях». 2006 г. 47-й ежегодный симпозиум IEEE по основам информатики (FOCS'06) . стр. 459–468. CiteSeerX 10.1.1.142.3471 . дои : 10.1109/FOCS.2006.49 . ISBN 978-0-7695-2720-8 .
^ Jump up to: ^а ^б Малков Юрий; Пономаренко Александр; Логвинов Андрей; Крылов, Владимир (2012), Наварро, Гонсало; Пестов, Владимир (ред.), «Масштабируемый распределенный алгоритм для задачи приближенного поиска ближайших соседей в многомерных общих метрических пространствах» , «Поиск по подобию и приложения» , том. 7404, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 132–147, doi : 10.1007/978-3-642-32153-5_10 , ISBN 978-3-642-32152-8 , получено 16 января 2024 г.
^ Jump up to: ^а ^б Малков Юрий; Яшунин, Дмитрий (2016). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графиков маленького мира». arXiv : 1603.09320 [ cs.DS ].
^ Jump up to: ^а ^б Малков Ю А.; Яшунин Д.А. (01.04.2020). «Эффективный и надежный приблизительный поиск ближайших соседей с использованием иерархических навигационных графов маленького мира» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 42 (4): 824–836. arXiv : 1603.09320 . дои : 10.1109/TPAMI.2018.2889473 . ISSN 0162-8828 . ПМИД 30602420 .
^ Арья, Сунил; Маунт, Дэвид (1993). «Приблизительные запросы ближайших соседей в фиксированных измерениях». Материалы четвертого ежегодного симпозиума {ACM/SIGACT-SIAM} по дискретным алгоритмам, 25–27 января 1993 г., Остин, Техас. : 271–280.
^ Оливье, Бомонт; Кермаррек, Анн-Мари; Маршал, Лорис; Ривьер, Этьен (2006). «Voro Net : масштабируемая объектная сеть на основе тесселяций Вороного» (PDF) . 2007 Международный симпозиум IEEE по параллельной и распределенной обработке . Том. РР-5833. стр. 23–29. дои : 10.1109/IPDPS.2007.370210 . ISBN 1-4244-0909-8 . S2CID 8844431 .
^ Оливье, Бомонт; Кермаррек, Анн-Мари; Ривьер, Этьен (2007). «Одноранговые многомерные наложения: аппроксимация сложных структур». Принципы распределенных систем . Конспекты лекций по информатике. Том. 4878. стр. 315–328. CiteSeerX 10.1.1.626.2980 . дои : 10.1007/978-3-540-77096-1_23 . ISBN 978-3-540-77095-4 .
^ Малков Юрий; Пономаренко Александр; Крылов Владимир; Логвинов, Андрей (2014). «Приблизительный алгоритм ближайшего соседа, основанный на навигационных графах маленького мира». Информационные системы . 45 : 61–68. дои : 10.1016/j.is.2013.10.006 . S2CID 9896397 .
^ Туссен, Годфрид (1980). «Относительный граф окрестности конечного плоского множества». Распознавание образов . 12 (4): 261–268. Бибкод : 1980PatRe..12..261T . дои : 10.1016/0031-3203(80)90066-7 .
^ А. Раджараман и Дж. Ульман (2010). «Анализ больших наборов данных, глава 3» .
^ Вебер, Роджер; Блотт, Стивен. «Структура данных на основе аппроксимации для поиска по сходству» (PDF) . S2CID 14613657 . Архивировано из оригинала (PDF) 4 марта 2017 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Рамасвами, Шарад; Роуз, Кеннет (2007). «Адаптивное ограничение кластерного расстояния для поиска сходства в базах данных изображений». ИКИП .
^ Рамасвами, Шарад; Роуз, Кеннет (2010). «Адаптивное ограничение кластерного расстояния для многомерной индексации». ТКДЕ .
^ Арья, С.; Маунт, ДМ ; Нетаньяху, Н.С. ; Сильверман, Р.; Ву, А. (1998). «Оптимальный алгоритм приблизительного поиска ближайшего соседа» (PDF) . Журнал АКМ . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . дои : 10.1145/293347.293348 . S2CID 8193729 . Архивировано из оригинала (PDF) 3 марта 2016 г. Проверено 29 мая 2009 г.
^ Кларксон, Кеннет Л. (1983), «Быстрые алгоритмы решения проблемы всех ближайших соседей», 24-й симпозиум IEEE. Основы компьютерных наук (FOCS '83) , стр. 226–232, doi : 10.1109/SFCS.1983.16 , ISBN 978-0-8186-0508-6 , S2CID 16665268 .
^ Вайдья, премьер-министр (1989). « Алгоритм O ( n log n ) для задачи всех ближайших соседей» . Дискретная и вычислительная геометрия . 4 (1): 101–115. дои : 10.1007/BF02187718 .

Источники

Эндрюс, Л. (ноябрь 2001 г.). «Шаблон задачи о ближайшем соседе» . Журнал пользователей C/C++ . 19 (11): 40–49. ISSN 1075-2838 .
Арья, С.; Маунт, ДМ ; Нетаньяху, Н.С. ; Сильверман, Р .; Ву, А.Ю. (1998). «Оптимальный алгоритм для приблизительного поиска ближайших соседей в фиксированных измерениях». Журнал АКМ . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . дои : 10.1145/293347.293348 . S2CID 8193729 .
Бейер, К.; Гольдштейн, Дж.; Рамакришнан, Р.; Шафт, У. (1999). «Когда имеет смысл ближайший сосед?». Материалы 7-й МКДТ .
Чен, Чунг-Мин; Лин, Ибэй (2002). «Оценщик на основе выборки для запросов Top-k». ИКДЕ : 617–627.
Самет, Х. (2006). Основы многомерных и метрических структур данных . Морган Кауфманн. ISBN 978-0-12-369446-1 .
Зезула, П.; Амато, Г.; Донал, В.; Батько, М. (2006). Поиск по сходству – подход метрического пространства . Спрингер. ISBN 978-0-387-29146-8 .

Дальнейшее чтение

Шаша, Деннис (2004). Высокопроизводительное обнаружение во временных рядах . Берлин: Шпрингер. ISBN 978-0-387-00857-8 .

Внешние ссылки

«Ближайшие соседи и поиск по сходству» - веб-сайт, посвященный образовательным материалам, программному обеспечению, литературе, исследователям, открытым проблемам и событиям, связанным с поиском NN. Ведёт Юрий Лифшиц
Wiki для поиска по сходству - коллекция ссылок, людей, идей, ключевых слов, статей, слайдов, кода и наборов данных о ближайших соседях.

[Cayton2008-1] Кейтон, Лоуэренс (2008). «Быстрый поиск ближайшего соседа для расхождений Брегмана». Материалы 25-й Международной конференции по машинному обучению . стр. 112–119. дои : 10.1145/1390156.1390171 . ISBN 9781605582054 . S2CID 12169321 .

[2] Цю, Дэюань, Стефан Мэй и Андреас Нюхтер. «Поиск ближайшего соседа с ускорением на графическом процессоре для 3D-регистрации». Международная конференция по системам компьютерного зрения. Шпрингер, Берлин, Гейдельберг, 2009 г.

[3] Беккер, Дукас, Гама и Лаарховен. «Новые направления поиска ближайших соседей с применением решетчатого просеивания». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (стр. 10–24). Общество промышленной и прикладной математики.

[panSearch-4] Jump up to: ^а ^б Бьюли, А.; Апкрофт, Б. (2013). Преимущества использования структуры проекции для сегментации плотных трехмерных облаков точек (PDF) . Австралийская конференция по робототехнике и автоматизации.

[5] Вебер, Роджер; Шек, Ханс-Дж.; Блотт, Стивен (1998). «Количественный анализ и исследование эффективности методов поиска по сходству в пространствах большой размерности» (PDF) . VLDB '98 Материалы 24-й Международной конференции по очень большим базам данных . стр. 194–205.

[6] Эндрю Мур. «Вводное руководство по деревьям KD» (PDF) . Архивировано из оригинала (PDF) 3 марта 2016 г. Проверено 3 октября 2008 г.

[Lee1977-7] Ли, DT ; Вонг, СК (1977). «Анализ наихудшего случая для поиска областей и частичных областей в многомерных двоичных деревьях поиска и сбалансированных квадродеревьях». Акта Информатика . 9 (1): 23–29. дои : 10.1007/BF00263763 . S2CID 36580055 .

[8] Руссопулос, Н.; Келли, С.; Винсент, Рузвельт (1995). «Запросы ближайших соседей». Материалы международной конференции ACM SIGMOD 1995 года по управлению данными – SIGMOD '95 . п. 71. дои : 10.1145/223784.223794 . ISBN 0897917316 .

[9] Андони, А.; Индик, П. (01 октября 2006 г.). «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерностях». 2006 г. 47-й ежегодный симпозиум IEEE по основам информатики (FOCS'06) . стр. 459–468. CiteSeerX 10.1.1.142.3471 . дои : 10.1109/FOCS.2006.49 . ISBN 978-0-7695-2720-8 .

[:1-10] Jump up to: ^а ^б Малков Юрий; Пономаренко Александр; Логвинов Андрей; Крылов, Владимир (2012), Наварро, Гонсало; Пестов, Владимир (ред.), «Масштабируемый распределенный алгоритм для задачи приближенного поиска ближайших соседей в многомерных общих метрических пространствах» , «Поиск по подобию и приложения» , том. 7404, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 132–147, doi : 10.1007/978-3-642-32153-5_10 , ISBN 978-3-642-32152-8 , получено 16 января 2024 г.

[:0-11] Jump up to: ^а ^б Малков Юрий; Яшунин, Дмитрий (2016). «Эффективный и надежный приблизительный поиск ближайшего соседа с использованием иерархических навигационных графиков маленького мира». arXiv : 1603.09320 [ cs.DS ].

[:2-12] Jump up to: ^а ^б Малков Ю А.; Яшунин Д.А. (01.04.2020). «Эффективный и надежный приблизительный поиск ближайших соседей с использованием иерархических навигационных графов маленького мира» . Транзакции IEEE по анализу шаблонов и машинному интеллекту . 42 (4): 824–836. arXiv : 1603.09320 . дои : 10.1109/TPAMI.2018.2889473 . ISSN 0162-8828 . ПМИД 30602420 .

[13] Арья, Сунил; Маунт, Дэвид (1993). «Приблизительные запросы ближайших соседей в фиксированных измерениях». Материалы четвертого ежегодного симпозиума {ACM/SIGACT-SIAM} по дискретным алгоритмам, 25–27 января 1993 г., Остин, Техас. : 271–280.

[voroNet-14] Оливье, Бомонт; Кермаррек, Анн-Мари; Маршал, Лорис; Ривьер, Этьен (2006). «Voro Net : масштабируемая объектная сеть на основе тесселяций Вороного» (PDF) . 2007 Международный симпозиум IEEE по параллельной и распределенной обработке . Том. РР-5833. стр. 23–29. дои : 10.1109/IPDPS.2007.370210 . ISBN 1-4244-0909-8 . S2CID 8844431 .

[rayNet-15] Оливье, Бомонт; Кермаррек, Анн-Мари; Ривьер, Этьен (2007). «Одноранговые многомерные наложения: аппроксимация сложных структур». Принципы распределенных систем . Конспекты лекций по информатике. Том. 4878. стр. 315–328. CiteSeerX 10.1.1.626.2980 . дои : 10.1007/978-3-540-77096-1_23 . ISBN 978-3-540-77095-4 .

[msw2014-16] Малков Юрий; Пономаренко Александр; Крылов Владимир; Логвинов, Андрей (2014). «Приблизительный алгоритм ближайшего соседа, основанный на навигационных графах маленького мира». Информационные системы . 45 : 61–68. дои : 10.1016/j.is.2013.10.006 . S2CID 9896397 .

[17] Туссен, Годфрид (1980). «Относительный граф окрестности конечного плоского множества». Распознавание образов . 12 (4): 261–268. Бибкод : 1980PatRe..12..261T . дои : 10.1016/0031-3203(80)90066-7 .

[18] А. Раджараман и Дж. Ульман (2010). «Анализ больших наборов данных, глава 3» .

[19] Вебер, Роджер; Блотт, Стивен. «Структура данных на основе аппроксимации для поиска по сходству» (PDF) . S2CID 14613657 . Архивировано из оригинала (PDF) 4 марта 2017 г. {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[20] Рамасвами, Шарад; Роуз, Кеннет (2007). «Адаптивное ограничение кластерного расстояния для поиска сходства в базах данных изображений». ИКИП .

[21] Рамасвами, Шарад; Роуз, Кеннет (2010). «Адаптивное ограничение кластерного расстояния для многомерной индексации». ТКДЕ .

[22] Арья, С.; Маунт, ДМ ; Нетаньяху, Н.С. ; Сильверман, Р.; Ву, А. (1998). «Оптимальный алгоритм приблизительного поиска ближайшего соседа» (PDF) . Журнал АКМ . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . дои : 10.1145/293347.293348 . S2CID 8193729 . Архивировано из оригинала (PDF) 3 марта 2016 г. Проверено 29 мая 2009 г.

[23] Кларксон, Кеннет Л. (1983), «Быстрые алгоритмы решения проблемы всех ближайших соседей», 24-й симпозиум IEEE. Основы компьютерных наук (FOCS '83) , стр. 226–232, doi : 10.1109/SFCS.1983.16 , ISBN 978-0-8186-0508-6 , S2CID 16665268 .

[Vaidya-24] Вайдья, премьер-министр (1989). « Алгоритм O ( n log n ) для задачи всех ближайших соседей» . Дискретная и вычислительная геометрия . 4 (1): 101–115. дои : 10.1007/BF02187718 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]