Кластерная индексация файлов для оптимизации поиска информации в распределенной файловой системе

1. Кластерная индексация файлов для оптимизации поиска информации в распределенной файловой системе

КЛАСТЕРНАЯ ИНДЕКСАЦИЯ ФАЙЛОВ
ДЛЯ ОПТИМИЗАЦИИ ПОИСКА
ИНФОРМАЦИИ В РАСПРЕДЕЛЕННОЙ
ФАЙЛОВОЙ СИСТЕМЕ
Кушвид Евгений Сергеевич
ст. гр. СШИм-15-1
Руководитель:
к.т.н., доцент
Чалая Лариса Эрнестовна

2. Актуальность:

02 / 24
• Высокие темпы роста объема текстовой информации
• Накопление неклассифицированных данных в
распределенной структуре
• Отсутствие возможности оптимального смыслового
определения архитектуры классов
• Необходимость в высококачественном и быстром
поиске по большому массиву документов

3. Цель:

03 / 24
Цель:
Целью работы является разработка метода
эффективного поиска текстовой информации в
распределенной файловой системе с высокой
производительностью и качеством при малых
ресурсных затратах приложения

4. Общая архитектура

04 / 24
Общая архитектура
Предобработка
Сбор и очистка
данных
Формирование
входного
вектора для
кластеризатора
Кластеризация
Формирование
структуры
кластеров
Повторение
для каждого
кластера
Поиск
Кластеризация
запроса
Ранжирование
результатов

5. Выборка:

Иерархическая структурированная библиотека
открытая для скачивания объемом 21гб
05 / 24

6. Сбор и очистка данных:

Стемминг
Удаление
стоп-слов
Очистка от
спецсимволов
Данные
06 / 24
Полученные
очищенные слова
данные отравляются
На формирование
входного вектора

7. Формирование входного вектора для кластеризатора

Полученный
массив слов
Частота их
встречаемости
Входной
вектор для
анализа
07 / 24

8. Существующие подходы к кластеризации:

Алгоритм
k-средних
Нейронная
сеть
Кохонена
FOREL
SOINN
08 / 24

9. Существующие подходы к индексации

09 / 24
Существующие подходы к индексации
Прямой индекс
Инвертированный
индекс

10. Обоснование выбранного решение:

SOINN
• Устойчивость к шумам
• Скорость
• Точность
• Адаптивность
• Отсутствие необходимости в эвристиках
10 / 24

11. Формирование структуры кластеров

Кластеризация
Выделения
подкластеров
Индексация
кластеров
11 / 24

12. Индексация

12 / 24
Каждому кластеру присваивается уникальный индекс в
порядке вложенности
Пределом кластеризации является сведение к один
кластер это один файл и таким образом можно
определить вложенность кластеров как уникальный
HASH

13. Пример иерархической индексированной кластерной структуры файлов

13 / 24
0000
0001
0001
0002
0002
0001
0003
0002
0001
0001
0002
0001
0003
0001
0002
0002
0001
0002
0002
По окончанию иерархической кластеризации каждый файл отделяется в
отдельный персональный кластер
(исключение: файлы дубликаты/копии)
Индекс файла со звездочкой: 0001000300020002

14. Пример вида метаинформации в документе

14 / 24

15. Пример сохраненной метаинформации в текстовом файле

15 / 24

16. Поиск

16 / 24
Поиск
Введение
поискового
запроса
Кластеризация и
определение
индекса иерархии
кластеров
Получение
искомого
файла

17. Имплементация:

17 / 24

18. Визуальный интерфейс

18/ 24

19. Поисковый запрос

19 / 24

20. Расширение поискового запроса

20 / 24

21. Экран настроек

21 / 24

22. Анализ эффективности:

Объем выборки
Средняя загрузка оперативной памяти
Максимальная загрузка оперативной памяти
Среднее время кластеризации
Среднее время иерархической кластеризации
Среднее время поиска
Среднее время поиска с ранжированием
22 / 24
21гб
400мб
1,5гб
7 мс
18 мс
19 мс
23 мс

23. Сравнительная характеристика алгоритмов поиска

23 / 24

24. Выводы

Недостатки
Достоинства