Диссертация (1137145), страница 8
Текст из файла (страница 8)
Так же существуют приближенные постановки этой задачи. Водном из вариантов допускается, что будут возвращены не обязательно всеистинноk-ближайшихэлементов.Вдругомслучае,допускаетсявозвратить элементы, находящиеся на расстоянии 1 + (,k-closest),где k-closest - k-й истинно ближайший элемент из множества к . Когдафункция расстояния удовлетворяет аксиомам метрики (тождества,симметрии,неравенствотреугольника),тоговорятпропоисквметрическом пространстве. В случае, когда хотя бы одна из аксиомможет нарушаться, то в литературе принято использовать термин поиск внеметрическом пространстве [Boytsov L., Naidan B., 2013] или поиск всемиметрическом пространстве.В любой постановке эта задача имеет тривиальное решение. Достаточновычислить расстояние между и каждым объектом из множества , приэтом запоминая либо k-ближайших, либо все объекты, которые лежат врадиусе .
Однако функция может быть вычислительно затратнойоперацией, а множество быть достаточно большим. Поэтому влитературе [Knuth D.E., с. 563],[Zezula P., Amato G., и др. 2006] обычно подзадачей поиска ближайшего соседа понимают именно задачу построенияструктуры данных над конечным множеством ⊂ , так чтобыоперация поиска ближайшего объекта среди множества к заданномуобъекту (запросу) ∈ требовала как можно меньше вычисленийфункции .46Можно сказать, что поиск ближайшего соседа является формулировкойзадачи поиска в самом общем виде.
Например, запросы вида "найтимаксимальный элемент во множестве", "найти все элементы множествалежащих в интервале [A;B]" могут быть выражены в терминах поискаближайшего соседа.Вкачествесамойтривиальнойструктуры можетслужитьобыкновенный массив или односвязный список. Сложность добавления внего новых элементов (1). Но для того чтобы определить, какой элементявляется ближайшим к , необходимо вычислить расстояние до каждогоэлемента из , что эквивалентно сложности поиска (), где – мощность .
Линейный список легко может быть развернут на распределенномоборудовании, однако сложность операции поиска () во многих случаяхможет является не приемлемой для построения масштабируемых решений(Опыт Gnutella). Стоит отметить, что полный перебор эффективнеереализовывать без помощи каких-либо структур. Достаточно множество равномерно распределить между вычислительными узлами и поискближайшего элемента к производить параллельно.Ранее в литературе было известно множество структур данных длярешения задачи как в точной постановке, так в приближенном варианте.Однако большинство из них изначально не ориентированы на работу нараспределённом оборудовании и были спроектированы для работы врамках одного вычислителя.
Как правило, такие структуры данных имеютвид дерева. Наличие корневого элемента, на котором «завязаны» всеалгоритмы структуры, является главным препятствием для построениядецентрализованных решений.2.2 Общее описание предлагаемой структуры данныхСтруктура MSW строится над конечным множеством в виде графаG(V, E). Объектам из множества однозначно сопоставляются вершины из47множества . Таким образом, операция поиска ближайшего объекта вомножестве к заданному , сводится к поиску вершины в графе .Основная идея заключается в том, чтобы зафиксировать некоторыйалгоритм поиска и так формировать структуру графа, чтобы он был«удобен» для этого алгоритма поиска.
В качестве базового алгоритмапоиска предлагается зафиксировать алгоритм GreedyWalk. Более того,желательно построить граф с такой структурой, чтобы поиск, от случайнойвершины, приводил к искомой вершине за логарифмическое число шагов сбольшой вероятностью.Для того чтобы жадный поиск гарантированно приходил к искомойвершине, достаточно, чтобы граф содержал в себе подграф Делоне. ГрафДелоне является двойственной структурой к диаграмме Вороного истроится он следующим образом: две вершины i и j соединяются ребром втом случае, если области вороного соответствующие точкам i и j являютсясмежными т.е. имеют общую границу.Однако, количество смежных областей с произвольно выбраннойобластьюiрастётэкспоненциальносувеличениемразмерностипространства, соответственно и количество ребер в графе Делоне такжерастет экспоненциально.
Более того, доказано [G. Navarro, 1999], чтоиспользуя лишь значения метрики, точно найти его невозможно. Поэтомубыло предложено, строить его аппроксимацию.K-Graph (граф в котором каждая вершина соединена с k ближайшими)является одной из таких конструкций, которая может служить в качествеаппроксимации графа Делоне. Важно, что она может быть построена дляпроизвольныхметрическихисемиметрическихпространствбезиспользования векторного представления данных.Интуитивно, начиная поиск от произвольной вершины, переходя отодной области Вороного, к другой в среднем необходимо совершить /2шагов. Поэтому для того, чтобы поиск был быстрым в графе, должнысодержаться длинные ребра, соединяющие с друг с другом области48Вороного, находящиеся в различных частях пространства. Таким образом,выделяется два типа ребер: длинные и короткие.
Короткие составляютаппроксимированный подграф Делоне и обеспечивают корректностьработы жадного алгоритма; длинные ребра необходимы для быстрогопоиска.2.3 Базовый алгоритм поиска ближайшего соседаВ качестве базового алгоритма поиска используетсяалгоритмGreedyWalk, идея которого во многом схожа с широко известным методомградиентного спуска.
Блок-схема алгоритма приведен на рисунке 15.Целью алгоритма GreedyWalk является обнаружение вершины в графе(, ) ближайшей к запросуq. Алгоритм принимает на вход двапараметра: запрос q ∈ D и вершину p0 ∈ V , с которой начинается поиск,также называемой точкой входа. Вершину в которой останавливаетсяжадный алгоритм будем называть локальным минимумом. Алгоритмработаетитеративно.Накаждойитерации,вычисляется расстояние между запросомокрестности N G ( p) вершиныp (qназываемойшагом,и всеми вершинами изN G ( p) = {x ∈ VG : ( p, x) ∈ EG } ).окрестности N G ( p) выбирается вершина pnext расстояние от запросаИзqдокоторой минимально. В случае если N G ( p) содержит вершину, котораяближе кq , чем p , итерация повторяется присваивая p равнойближайшей вершине к q из множества N G ( p) . В другом случае, когда вокрестности p N G ( p) нет вершины, которая была бы ближе к запросу, чемp , поиск останавливается и p возвращается в качестве искомой вершины.49Рис.
15. «Жадный» алгоритм поиска GreedyWalk. Итеративная версия.Вершину в которой останавливается алгоритм GreedyWalk можнорассматривать в качестве локального минимума относительно запроса q.Последовательность вершин выбранных алгоритмом качестве pnext есть!путь в графе , обозначим его как ! ! . Вычислительная сложностьалгоритма ограниченна сверху суммой степеней вершин входящих в путь!! ! .В свою очередь не сложно показать, что максимальная степеньвершины ограничена величиной (log ()). Пологая что все перестановки50последовательности входных данных равно вероятны можно оценить длявершины добавленной в момент времени 0 < < математическоеожидание числа установленных связей c вершинами добавленным вовремя + 1, + 2, … , Таким образом, предполагая что длинна пути естьтакже величина ограниченная (log ()), можно сделать предположение отом, что общая вычислительная сложность алгоритма имеет вид(log ! ).
Данные предположения эмпирически проверяются в главе 3.Так же возможна рекурсивная реализации «жадного» алгоритмаGreedyWalk. Псевдокод рекурсивной версии приведен на рисунке 160 GreedyWalkRecursion(q: object, entry_point: object)1 vcurr ← entry_point; δcurr ← (q, vcurr)2 δmin ← δ(q, vcurr); vnext:=NIL;3 foreach vcurr’∈vcurr.getNeighbors() do4δcurr’:=(query, vfriend);5if δcurr’<δmin then6δmin:=δcurr’;7vnext:=vcurr’;8if vnext = NULL then return vcurr;9 else return GreedyWalkRecursion (q, vnext);Рис. 16.
Рекурсивная версия «жадного» алгоритма GreedyWalkЭлемент, являющийся локальный минимум относительно запроса ,может совпадать с глобальным минимумом, то есть с ближайшимэлементом к запросу среди всех элементов множества , но может и несовпадать. Если бы каждая вершина в структуре имела в своей окрестностивсе элементы, чьи области Вороного граничат с её собственной, то этоисключало бы существование локальных минимумов не являющихсяглобальными.Поддержание этого условия эквивалентно построениюграфа Делоне, который является двойственным к диаграмме Вороного.Поскольку доказано что, для абстрактных метрических пространствопределение точного графа Делоне является невозможным [Navarro G.,1999], то избежать существования локальных минимумов не удается.51Но для задачи неточного поиска, определенной выше, это не играетсущественной роли.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
