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

Поиск ближайшего соседа ( 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-данные были организованы посредством проекции на двумерную сетку, и предполагает, что данные пространственно гладкие в соседних ячейках сетки, за исключением границ объекта. Эти предположения справедливы при работе с данными 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 Search по сходству - коллекция ссылок, людей, идей, ключевых слов, статей, слайдов, кода и наборов данных о ближайших соседях.

[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 ]