Диссертация (1137145), страница 7
Текст из файла (страница 7)
В оригинальнойреализации авторами использовалось 1000 лучей. Псевдокод алгоритмарасчёта объёма области Вороного c помощью метода Монтекарлоприведен на рисунке 12.calcVolume(SET[object] , object )01 SET [double] ⟵ ∅02 SET [rays] ⟵ createRays()03 foreach ∈ do04double ⟵ ∞05foreach ! ∈ do06double ⟵ compDistOnRay(, ! )07if < then08⟵09endif10endfor11 ⟵∪12 endfor13 return!"##$%#× !∈! !!|!|Рис. 12.
Алгоритм вычисления объёма области Вороного c помощью методаМонтекарлоВ оригинальной статье авторы приводят также другой более быстрыйспособ вычисления наилучшей аппроксимации области Вороного (рисунок13)Его общая вычислительная сложность линейна относительнофиксированной размерности . В отличии от наивного алгоритмаupdate_naive, лучи для каждого взятого объекта вычисляются только одинраз.
Каждый узел поддерживает двудольный граф , на одной долекоторого располагаются объекты множества . , на другой доле –множество лучей . . Для каждого луча выпущенного из точки выделают объект ! (), чья область Вороного будет пересечена первойлучом . Похожим образом {! (! )} обозначают множество лучейвыпущенных из , для которых область Вороного объекта ! будетпересекаться первой.40update(SET[object] ! . , object )01 MAP [ray->object] improve ⟵ ∅02 SET [(object,double)] volumes⟵ ∅03 foreach ∈ . do04double ! ⟵ ! ()05object !! ⟵ NULL05foreach ! ∈ ! .
∖ . do06double ⟵ compDistOnRay(, ! )07if < ! then08! ⟵ 10!! ⟵ !09endif10endfor11if !! ≠ NULL then11improve[]⟵ !!12 endfor13 foreach ! ∈ ! . ∖ . do14volumes⟵volumes∪(! ,calcVolume(! . ∪ . \! ,))15 endfor16 sort volumes by decreasing volume13 . ⟵ {! . , }19 update ! , !Рис. 13. Алгоритм вычисления объёма области Вороного c помощью методаМонтекарло1.3 ВыводыТехнология DHT является мощным инструментом и находит своеприменениевомножествеприложений,вкоторыхтребуетсяотказоустойчивость, сбалансированность нагрузки, распределенность имасштабируемость. Существует множество реализаций этой концепции.
Вданном разделе были разобрана три из них Chord, Kademlia и Pastry.Нерассмотренными остались CAN, Koord, P-Grid, Tapestry, однако ониupdate_naive(SET[object] ! . , object )01 double current_vol ⟵ calcVolume(. , )02 foreach ∈ ! ! . ∪ . do03double vol ⟵ calcVolume(, )04if vol < current_vol then05. ⟵ 06current_vol ⟵ vol07endif08 endforРис. 14 Алгоритм вычисления объёма области Вороного c помощью методаМонтекарло41принципиальных отличий не имеют.Различные реализации DHT отличаются мерой близости вычисляемоймежду идентификаторами, однако все они имеют схожую структурутаблицымаршрутизации,поддерживаемойнакаждомузле.Этообуславливается тем, что все реализации используют алгоритм поиска, восновекотороголежит"жадный"алгоритм.Чтобыобеспечитьлогарифмическую сложность поиска от общего числа узлов, структуратаблицы маршрутизации поддерживается так, чтобы на каждом шагеалгоритм поиска мог перейти к узлу с идентификатором более чем два разаблизким к искомому, чем идентификатор текущего узла.Несмотря на все достоинства, функциональность DHT ограниченапоиском на точное совпадения ключа.Такие операции как поиск нанеточное совпадение или поиск в заданном интервале напрямую неподдерживаютсяDHT.Функцияпоискананеточноесовпадение,например, поиск с учетом редактирования строки, может быть реализованаповерх DHT, добавляя всевозможные варианты написания поисковогоключа, либо параллельно осуществляя поиск всех вариантов написанияключа, но в любом случае это ведёт к крайне не эффективным решениям.Этот обстоятельство обуславливается тем, что в DHT системах неиспользуются напрямую значения ключей, а используются значения хэшфункции от изначальных ключей для того, чтобы обеспечить равномерноераспределение ключей на всём пространстве возможных ключей.
Этоприводит к тому, что изначальная семантика, которая могла содержаться взначениях ключей разрушается хэш-функцией.Во втором разделе были рассмотрены методы построения сетевыхструктуримеющийболеесильную(болееуниверсальную)функциональность поиска в сравнении с алгоритмами DHT, приведённых впервом разделе. Данные алгоритмы (работают с ключами имеющих видвектора) позволяют решать задачу поиска ближайшего соседа в векторномпространстве. То есть эти алгоритмы более сильные в том смысле, что42задача поиска на точное совпадения ключа, может быть сведена к поискуближайшей точке в векторном пространстве.МодельКлайнберагапозволяетзасложность(log ()! )децентрализованному алгоритму поиска обнаружить на целочисленной мерной целочисленный решетке узел с заданными координатами; Voronetобобщает модель Клайнберга и повзоляет идентифицировать узлы сетиточкамипространства ! ; RaynNet – улучшенная версия VoroNet,использует идею аппроксимации области Вороного методом Монте-Карло,позволяет на узлах хранить более компактные таблицы маршрутизации.Главным недостатком алгоритмов основанных на модели Кланберга,является то, что они опираются на предположение о равномерномраспределение объектов в пространстве и поэтому неспособны справлятьсяс распределениями сильно отличающимися от равномерного.
Более того,все рассмотренные в главе алгоритмы, ограничены работой с объектамиимеющих векторное представление. В следующих главах данной работыбудут предложены алгоритмы организации данных и поиска не имеющихподобныхнедостатков,сохранивмасштабируемости.43свойствадецентрализациииГлава 2.
MSW – распределённая структура данных дляпоискаближайшегососедавметрическихпространствах.В данной главе делается шаг в сторону построения P2P протоколов внекотором смысле с максимально возможно широкими поисковымивозможностями.Рассматриваютсяалгоритмыпозволяющиеорганизовывать данные в виде сети и производить в ней поискk-ближайших объектов к объекту запросу на основании заданной мерыблизости децентрализованным образом.Таким образом, в качестве модели поиска рассматривается задачапоиска ближайшего соседа в метрическом пространстве, и как обобщение,задача поиска ближайшего соседа в семиметрических1 пространствах. Всепредлагаемые в главе алгоритмы, опираются только на вычислениезначений функции расстояния, заданной внешним образом, при это неиспользуя какие-либо дополнительные свойства пространства, например,векторное представление данных.Предлагаемые алгоритмы решают задачу организацию данных в видесети со структурой эффективной для поиска ближайшего соседа, поэтомусовокупность алгоритмов MSWConstruction и K-NNSearch рассматреваетсяв качестве структуры данных для поиска ближайшего соседа вметрическом пространстве, именуемой MSW (Metrized Small World).Так же как и во второй части главы 1, для описания алгоритмов будетиспользоватьсятерминологияграфов.Объектамизмножества однозначно сопоставляются вершины из множества графа (, ) .1В данном случае под термином семиметрическое пространство понимается метрическоепространство с функцией расстояния, которая может нарушать некоторые аксиомы метрическогопространства.
Например для некоторых троек объектов может не соблюдаться неравенство треугольника44Таким образом, операция поиска ближайшего объекта во множестве кзаданному , сводится к поиску вершины в графе .Модель метрического пространства, являясь более богатой структурой,имеет возможность лучше отражать логические взаимосвязи объектовпредметной области. Можно говорить, что поиск в метрическомпространстве имеет большую выразительную способность нежели, чемпоиск в векторном пространстве или поиск во множестве наделенноголинейным порядком.
Тем самым алгоритмы, использующие поискближайшего соседа в метрическом пространстве в качестве модели поискаимеют потенциально больший спектр применения.Так объектамиметрического пространства могут быть n-мерные вектора, графы, строки.Например, в качестве расстояния между векторами можно использоватьЕвклидово расстояние, либо ! норму или функцию обратную косинусуугла между векторами.
В качестве метрики для графов можноиспользовать расстояние редактирования, или, например, функциюоснованной на вычислении размера общего изоморфного подграфа. Длямножеств – расстояние Джакарда [P. Jaccard, 1901], для строк расстояниередактирование [E. S. Ristad, P. N. Yianilos, 1998], коэффициент Танимото[T. Tanimoto, 1958][D. R. Flower, 1998] и другие.Материалы главы в полной мере изложены в следующих публикациях:[Alexander Ponomarenko, Yury Malkov и et.al., 2016], [Пономаренко А.
А.,Мальков Ю. А. и др., 2012], [Ponomarenko A, 2015], [MalkovYury., Ponomarenko Alexander et.al., 2014], [Yury M., Ponomarenko A. et.al.,2012], [Ponomarenko A., Malkov Y. et.al., 2011], [Krylov V., LogvinovA., Ponomarenko A., Ponomarev D., 2008], [Ponomarenko A., Krylov V.,Logvinov A., Ponomarev D., 2008]2.1ФормулировказадачипоискаРазличные вариации.45ближайшегососеда.Задача поиска ближайшего соседа в метрическом пространствеформулируется следующим образом. Для заданной функции расстояния: × ⟶ ! определенной на множестве всевозможных объектов (domain), в заданном конечном множестве ⊂ требуется найтиближайший объект к заданному (запросу) ∈ .Существуют несколько вариаций этой задачи: поиск k-ближайших (knearest neighbor search) и поиск всех объектов в заданном радиусе (rangesearch).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
