Введение
Глава 1. Обзор алгоритмов распределенных систем хранения 13
1.1 Алгоритмы распределенных систем хранения с возможностью поиска на точное совпадение 13
1.1.1 Концепция распределенной хэш-таблицы 14
1.1.2 Протокол Chord 15
1.1.3 Протокол Kademlia 19
1.1.4 Pastry 24
1.1.5 Применения 27
1.2 Алгоритмы распределенных систем хранения с возможностью поиска ближайшего соседа в векторных пространствах 32
1.2.1 Модель навигационного тесного мира Клайнберга 33
1.2.2 VoroNet 35
1.2.3 Ray Net 38
1.3 Выводы 41
Глава 2. MSW - распределённая структура данных ля поиска ближайшего соседа в метрических пространствах 44
2.1 Формулировка задачи поиска ближайшего соседа. Различные вариации 45
2.2 Общее описание предлагаемой структуры данных 47
2.3 Базовый алгоритм поиска ближайшего соседа 49
2.4 Серия поисков 52
2.5 Алгоритм поиска к-ближайших соседей K-NNSearch 53
2.6 Алгоритм добавления 55
2.7 Алгоритм добавления основанный на устранении локальных минимумов 57
2.8 Процедура улучшения поисковых свойств сети за счёт использования информации о запросах 61
2.9 Выводы 61
Глава 3. Исследование свойств предложенных алгоритмов 62
3.1 Наборы данных 63
3.2 Исследование навигационных свойств: распределение длины кратчайшего пути и распределение длины пути совершаемой жадным алгоритмом 64
3.3 Средняя длина пути жадного алгоритма в графе в зависимости от числа элементов в структуре 74
3.4 Распределение степеней вершин 76
3.5 Коэффициент кластеризации 77
3.6 Вычислительная сложность и точность алгоритма поиска 78
3.7 MSW - как структура данных для поиска ближайшего соседа. Сравнительный анализ с другими структурами данных для поиска ближайшего соседа 82
3.7.1 Сравниваемые методы 82
3.7.2 Эксперименты 86
3.7.3 Методология оценки 87
3.8 Улучшения навигационных свойств графа с помощью процедуры RepairByQuery 92
3.9 Выводы 93
Глава 4. Математическая модель оптимальных графов для распределённого поиска 95
4.1 Предпосылки разработки модели 96
4.2 Модель 97
4.3 Алгоритм Табу-поиска решений предложенной модели 99
4.4 Результаты вычислительных экспериментов 101
4.5 Выводы 110
Глава 5. Архитектура программной платформы для исследования свойств распределённых алгоритмов для поиска в метрическом пространстве 111
5.1 Базовый абстрактный класс MetricElement 112
5.2 Интерфейс MetricElementFactory 113
5.3 Работа в n-мерном Евклидовом пространстве 114
5.4 Работа с частотными векторами текстов 114
5.5 Класс AbstractMetricStructure 115
5.6 Класс MetrizedSmallWorld 116
5.7 Класс SelfAdaptedMetrizedSmallWorld 116
5.8 Библиотека алгоритмов AlgoritmLib 117
5.9 Эксперименты над корпусом текстов Тгес-3 117
5.10 Многопоточная реализация экспериментов с точками d-мерного Евклидова пространства 121
5.11 Выводы 124
Заключение 125
Публикации по теме диссертации 127
Список литературы 129
Приложения 136
