Диссертация (1137145), страница 2
Текст из файла (страница 2)
Какправило, в качестве транспортного уровня выступает TCP/IP сеть. Каждыйузел P2P сети может быть вовлечён в процесс хранения и поиска, а такжелюбой узел может выступать в качестве инициатора поиска. В этомзаключается главная особенность структурированных P2P сетей, то есть враспределённойархитектуре,вкоторойотсутствуеткакой-либоцентральный элемент, ответственный за координацию работы всейсистемы.
Каждый узел хранит информацию только о небольшом числеузлов в сравнении с общим числом узлов в сети, тем не менее, сетьстроится таким образом, что операция поиска имеет логарифмическую(~()) вычислительную сложность относительно общего числа узлов .Даннаяособенностьпозволяетсоздаватьраспределенныесистемыхранения, имеющие возможность масштабироваться, как по нагрузке, так ипо вместимости.Теоретическимаспектампостроениямасштабируемыххранилищданных на основе P2P сетей посвящены работы J.
Klainberg, A-M.Kermarrec, O. Beaumont, I. Stoica, M. Ripeanu, P. Maymounkov, A. Rowstronи других специалистов.Известныеприменяемыевдлянастоящеевремяраспределенныхалгоритмыпоискамасштабируемыхданных,хранилищ,ограничены поиском на точное совпадение или же поиском ближайшего6соседа в Евклидовых пространствах. В свою очередь, алгоритмам поиска вболееобщемслучае–метрическихпространствахпосвященымногочисленные работы D. Knut, P. Zezula, S. Arya, E. Chavez, G. Navarro,G.
Amato, Ю. Лифшиц, А. Савченко, А. Бабенко и других специалистов.Однако, существующие методы поиска в метрических пространствахизначально разрабатывались без учёта требования эффективной работы вусловиях распределенного оборудования и как правило основываются наструктурах имеющих вид дерева или ассоциативного массива, которые всвою очередь, имеют присущие им проблемы масштабирования.Такимметрическихобразом,разработкапространствахдляалгоритмовпоискараспределённыхданныхвмасштабируемыххранилищ является актуальной задачей.Целью диссертационной работы является исследование и разработкаструктур для хранения данных в масштабируемых хранилищах иалгоритмов эффективного поиска данных методом ближайшего соседа,обладающих следующими свойствами:1.
Масштабируемость по количеству информационных объектов2. Масштабируемостьпроизводительностизасчётдобавлениявычислительных узлов3. Способность работать в условиях распределенного оборудования4. НезависимостьотформыпредставленияинформационныхобъектовДля достижения поставленной цели были сформулированы следующиезадачи диссертационной работы:1.
Разработать распределённый алгоритм построения графа снавигационными свойствами тесного мира, не использующийвекторное представление данных2. Провестиисследованиеформируемыхграфов(диаметр,коэффициент кластеризации, распределение степеней вершин).73. Разработать алгоритм улучшения навигационных свойств графа4. Разработать алгоритм поиска k-ближайших соседей в графе сосвойством навигационного тесного мира5. Провести эмпирический сравнительный анализ разработанныхалгоритмов с наиболее известными методами поиска ближайшегососеда.6.
Разработать математическую модель оптимальной конфигурациирёбер графа для поиска ближайшего соседа жадным алгоритмом7. Найтиточныематематическойиэвристическиемоделидлярешениянекоторыхпредложеннойчастныхслучаевцелочисленной решётки.8. Разработать программную реализацию предложенных алгоритмовна языке программирования Java.Объектом исследования являются масштабируемые хранилища данных.Предметом исследования являются структуры данных для построенияраспределенных хранилищ и эффективные алгоритмы поиска информациив таких хранилищах.Область исследованияВ части исследования и разработки структур данных и алгоритмов, длямасштабируемых хранилищ, работа соответствует пункту 2 паспортаспециальности05.13.17«Теоретическиеосновыинформатики»-Исследование информационных структур, разработка и анализ моделейинформационных процессов и структур.Разработка алгоритмов поиска информации соответствует также пункту9специальности 05.13.17.
– «Разработка новых интернет-технологий,включая средства поиска, анализа и фильтрации информации, средстваприобретения знаний и создания онтологии, средства интеллектуализациибизнес-процессов».8Методы исследованияДля решения поставленных задач использовались математические моделитеорииграфов,теориислучайныхграфов,методыдискретнойоптимизации, численные экспериментыНаучная новизна работы:1.
Разработаны и исследованы алгоритмы построения структур данныхдляраспределённыхмасштабируемыххранилищ,отличающиесяиспользованием графов со свойствами навигационного тесного мира,позволяющие эффективно осуществлять поиск ближайшего соседа вметрическом пространстве.2. Предложен алгоритм модификации графа в реальном времени,позволяющий улучшать поисковые свойства путём обнаружение иустранения локальных минимумов, отличающийся использованиеминформации о поступающих запросах на этапе исполнения.3. Разработан алгоритм, позволяющий производить поиск k-ближайшихсоседейвметрическомпространстве,использующийтольковычисление меры близости между информационными объектами и неиспользующий векторное представление данных, в отличие отсуществующих алгоритмов.4.
Разработанаматематическаяоптимальнуюмодель,конфигурациюрёберпозволяющаяграфа,находитьотличающаясяиспользованием в качестве целевой функции оценки вычислительнойсложности алгоритма поиска ближайшего соседа GreedyWalk.Достоверностьиобоснованностьрезультатовопределяетсяиспользованием корректного математического аппарата и обеспечиваетсяэкспериментальнойпроверкой.Всеисходныекодыпрограмм,используемые для получения результатов, приводимые в работе, находятсяв свободном доступе.Реализация и внедрение работы9Предложенные в диссертации алгоритмы были использованы вследующих разработанных при участии автора программных продуктах:«Skoal – Система поиска химических соединений по структурномусходству». Подтверждено свидетельством о государственной регистрациипрограммы для ЭВМ №2012619905.«Cloud MSW – Система облачного хранения данных с возможностьюпоиска в метрическом пространстве».
Подтверждено свидетельством огосударственной регистрации программы для ЭВМ №2012612167.«Non-Metric Space Library» - открытая свободно-распространяемаябиблиотека методов поиска ближайшего соседа доступная по адресуhttps://github.com/searchivarius/nmslib.Результаты исследований внедрены в отчеты по выполнению научноисследовательских работ при поддержки следующих грантов:Грант Правительства Российской Федерации для государственнойподдержкинаучныхисследований,проводимыхподруководствомведущих ученых в российских образовательных организациях высшегообразования (договор № 11.G34.31.0057 от 21 октября 2011 г.).Подтверждено «Актом внедрения результатов исследований».Грант РНФ 14-41-00039. Подтверждено «Актом внедрения результатовисследований».Апробация результатов исследованияОсновные положения диссертации были представлены и доложены наследующих научных конференциях и семинарах:1.
Workshop on Critical and collective effects in graphs and networks(Москва, Россия, 2016)2. 8th International Conference on Similarity Search and Applications(Глазго, Великобритания, 2015).3. XVI-яБайкальскаямеждународнаяшкола-семинар"Методыоптимизации и их приложения" (о. Ольхон, Иркутская область,Россия, 2015).104. The 4th International Conference on Network Analysis (НижнийНовгород, 2015).5. 5th International Conference on Similarity Search and Applications(Торонто, Канада, 2012)6. InternationalConferenceonInformationandCommunicationTechnologies and Applications ICTA 2011 (Орландо, Флорида, США,2011).Основные положения, выносимые на защиту1. АлгоритмыпостроенияграфаMSWConstructionиСonstuctionByReparing2.
Алгоритм K-NNSearch для поиска k-ближайших соседей вметрическом пространстве3. Алгоритмулучшенияпоисковыхсвойствграфанаэтапеисполнения запросов RepairByQuery4. Математическая модель оптимальной конфигурации рёбер графадля поиска ближайшего соседа алгоритмом GreedyWalk.5. Реализация алгоритмов на языке программирования Java.Публикации результатов исследованияПо теме диссертации опубликовано 16 работ, в том числе 8 работ визданиях, рекомендованных ВАК [1-2], из них 6 работ в рецензируемыхжурналахиндексируемыесистемойScopus[3-8],полученодвасвидетельства о государственной регистрации программ для ЭВМ [12-13].Личный вклад автораАвтору принадлежит лично алгоритм построения графов со свойстваминавигационного тесного мира MSWConstruction, алгоритм поиска kближайших соседей K-NNSearch, а также алгоритм улучшения поисковыхсвойств структуры на этапе исполнения запросов RepairByQuery.
При его11участиибыларазработанамодельоптимальнойструктурыдлявычислительно эффективного поиска. Им лично выполнены программныеразработкиалгоритмовипроведеныосновныеэкспериментальныеисследования. Им лично и при его участии выполнена подготовкапубликацийпопредставленнойработеидокладовнанаучныхконференциях и семинарах.Структура и объем работыДиссертация состоит из введения, пяти глав, заключения, спискаиспользованной литературы из 69 наименований.
Общий объем работы136 страницы текста, содержащего 58 рисунка (включая описанияалгоритмов)12Глава 1. Обзор алгоритмов распределенных системхраненияВ данной главе делается обзор существующих алгоритмов лежащихв основе распределенных систем хранения данных. В первом разделе«Алгоритмы распределенных систем хранения с возможностью поиска наточное совпадение»рассматриваются алгоритмы лежащие в основетретьего поколения структурированных P2P сетей – DHT. Основнаяособенность структурированных P2P сетей заключается в том, что однатиповая операция поиска затрагивает только логарифмическое число узловO(log(n)), в отличие от неструктурированных P2P сетей таких как Gnutela,поиск в которых производится распространением поискового сообщенияиспользуяшироковещательнуюопрашиваниючислаузловстратегию,линейнокотораяприводитпропорциональномукобщемуколичеству [M.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
