Диссертация (1137145)
Текст из файла
СодержаниеСодержание...................................................................................................... 2Введение .......................................................................................................... 5Глава 1. Обзор алгоритмов распределенных систем хранения ................ 131.1 Алгоритмы распределенных систем хранения с возможностьюпоиска на точное совпадение .......................................................................
131.1.1 Концепция распределенной хэш-таблицы ................................ 141.1.2 Протокол Chord ............................................................................ 151.1.3 Протокол Kademlia ...................................................................... 191.1.4 Pastry..............................................................................................
241.1.5 Применения .................................................................................. 271.2 Алгоритмы распределенных систем хранения с возможностьюпоиска ближайшего соседа в векторных пространствах........................... 321.2.1 Модель навигационного тесного мира Клайнберга ................ 331.2.2 VoroNet......................................................................................... 351.2.3 RayNet .......................................................................................... 381.3 Выводы ................................................................................................. 41Глава 2.
MSW – распределённая структура данных для поискаближайшего соседа в метрических пространствах. ....................................... 442.1 Формулировка задачи поиска ближайшего соседа. Различныевариации. ........................................................................................................ 452.2 Общее описание предлагаемой структуры данных ........................ 472.3 Базовый алгоритм поиска ближайшего соседа ................................ 492.4 Серия поисков ..................................................................................... 522.5 Алгоритм поиска k-ближайших соседей K-NNSearch ....................
532.6 Алгоритм добавления ......................................................................... 5522.7 Алгоритм добавления основанный на устранении локальныхминимумов ..................................................................................................... 572.8Процедураулучшенияпоисковыхсвойствсетизасчётиспользования информации о запросах ...................................................... 612.9 Выводы ................................................................................................. 61Глава 3. Исследование свойств предложенных алгоритмов ....................
623.1 Наборы данных ................................................................................... 633.2 Исследование навигационных свойств: распределение длиныкратчайшего пути и распределение длины пути совершаемой жаднымалгоритмом. ................................................................................................... 643.3 Средняя длина пути жадного алгоритма в графе в зависимости отчисла элементов в структуре........................................................................
743.4 Распределение степеней вершин ....................................................... 763.5 Коэффициент кластеризации ............................................................. 773.6 Вычислительная сложность и точность алгоритма поиска ............ 783.7 MSW – как структура данных для поиска ближайшего соседа.Сравнительный анализ с другими структурами данных для поискаближайшего соседа.
...................................................................................... 813.7.1 Сравниваемые методы ................................................................. 823.7.2 Эксперименты .............................................................................. 863.7.3 Методология оценки .................................................................... 873.8 Улучшения навигационных свойств графа с помощью процедурыRepair_By_Query ...........................................................................................
923.9 Выводы ................................................................................................. 93Глава4.Математическаямодельоптимальныхграфовдляраспределённого поиска ................................................................................... 954.1 Предпосылки разработки модели ......................................................
964.2 Модель ................................................................................................. 974.3 Алгоритм Табу-поиска решений предложенной модели ................ 9934.4 Результаты вычислительных экспериментов ................................. 1014.5 Выводы ............................................................................................... 110Глава 5. Архитектура программной платформы для исследованиясвойствраспределённыхалгоритмовдляпоискавметрическомпространстве .................................................................................................... 1115.1 Базовый абстрактный класс MetricElement .................................... 1125.2 Интерфейс MetricElementFactory..................................................... 1135.3 Работа в n-мерном Евклидовом пространстве ...............................
1145.4 Работа с частотными векторами текстов ........................................ 1145.5 Класс AbstractMetricStructure ........................................................... 1155.6 Класс MetrizedSmallWorld ................................................................ 1165.7 Класс SelfAdaptedMetrizedSmallWorld ............................................ 1165.8 Библиотека алгоритмов AlgoritmLib ............................................... 1175.9 Эксперименты над корпусом текстов Trec-3 ................................. 1175.10 Многопоточная реализация экспериментов с точками d-мерногоЕвклидова пространства .............................................................................
1215.11 Выводы ............................................................................................. 124Заключение .................................................................................................. 125Публикации по теме диссертации .............................................................
127Список литературы ..................................................................................... 129Приложения ................................................................................................. 1364ВведениеВинформационно-вычислительныхсистемахвремядоступакинформации в хранилище данных во многом определяет скорость работывсей системы. Поэтому алгоритмы поиска данных в хранилищах должныподдерживать высокий уровень параллелизма и быть вычислительноэффективными.Технологиибольшихданныхтребуютотсистемоставаться эффективными как с увеличением объёма хранимых данных,так и с возрастающей скоростью их поступления.
Для многих приложений,особенно связанных с алгоритмами анализа данных и машинногообучения, практически весь объем хранилища должен поддерживаться вактивном состоянии и обеспечивать быстрое нахождение и чтение данных,как правило по принципу похожести с предъявляемыми образцами –запросами. Такой вид процессов в хранилищах называют поиском данныхна основе похожести (близости). Для этого на множестве всевозможныххранимых данных (domain) вводят функцию расстояния : × ⟶[!,!!) , отражающую семантику предметной области.
Тогда задачапостроения эффективного хранилища данных может быть сведена к задачепостроения структуры данных S над конечным множеством ⊂ ,позволяющей вычислительно эффективного производить поиск данных«по похожести». Другими словами структура данных S должна позволятьэффективно решать задачу поиска ближайшего соседа, то есть позволятьэффективно вычислять функциюargmin(σ (q, x)), где q ∈ D некоторыйx∈Xинформационный объект – запрос.Важный подкласс таких информационных хранилищ – это хранилища«ключ-значение». Такие системы главным образом поддерживают двеоперации: поиск и хранение данных по заданному ключу используя точноесовпадение.Нахранилищах«ключ-значение»основанымногиепопулярные Web-сервисы.
Например, система обмена сообщениями5Facebook и хранилище сообщений системы SoundCloud используютApache Cassandra; многие продукты Google – такие как Gmail, YouTube,Google Maps – основаны на системе BigTable, которая также являетсяхранилищем «ключ-значение».Одним из возможных подходов к построению масштабируемыххранилищивчастностихранилищ«ключ-значение»,являетсяиспользование и построение структурированных Peer-to-Peer (P2P-сетей).Посредством транспортного уровня, каждый узел P2P сети имеетвозможность передавать и принимать сообщение напрямую от любогодругого участника сети (от этого и происходит название Peer-to-Peer).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
