ВВЕДЕНИЕ
1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ ЗАДАЧИ ПОСТРОЕНИЯ
ИНВЕРТИРОВАННОГО ИНДЕКСА 6
1.1 Инвертированный индекс в поисковых системах 6
1.2.1 Алгоритмы построения инвертированного индекса 7
1.2.2 Инвертированный индекс в MapReduce 10
1.3 Парадигма MapReduce 12
1.4 Распределенная файловая система HDFS 20
2. АНАЛИЗ ТЕХНОЛОГИЙ ОБРАБОТКИ БОЛЬШИХ ДАННЫХ 24
2.1 Альтернативы технологии MapReduce 24
2.2 Сравнительный анализ технологий для обработки больших данных . 29
2.3 Выбор технологии для реализации алгоритма 31
3. ПРОЕКТИРОВАНИЕ И РАЗРАБОТКА АЛГОРИТМА ПОСТРОЕНИЯ ИНВЕРТИРОВАННОГО ИНДЕКСА НА МОДЕЛИ MAPREDUCE
3.1 Требования к разрабатываемой программе
3.2 Архитектура разрабатываемой программы
3.3 Разработка программы построения инвертированного индекса 37
3.4 Компиляция и запуск программы построения инвертированного
индекса в системе Hadoop 40
3.5 Сравнение с последовательной программой 42
ЗАКЛЮЧЕНИЕ 44
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ 46
ПРИЛОЖЕНИЕ_А. Листинг InvertedIndexDriver 49
С появлением вычислительной техники объем информации, с которой может работать человек, значительно увеличился. Еще более 30 лет назад учеными стали разрабатываться алгоритмы, позволяющие упростить работу с данными, а также получить из них новые, ранее неизвестные знания. Однако сегодня эти алгоритмы неэффективны, поскольку объемы информации стали слишком большими.
Для работы с большими объемами данных была разработана специальная система Apache Hadoop [1], Главное место в этой системе занимает технология под названием MapReduce. Реализация MapReduce позволяет производить распределенные вычисления над большими объемами данных в компьютерных кластерах эффективно и безотказно.
Системы, основанные на MapReduce, разработаны таким образом, чтобы параллельность вычислений была реализована не за счет суперкомпьютера, а за счет вычислительных кластеров - наборов стандартных аппаратных средств, соединенных между собой.
Актуальность бакалаврской работы обусловлена тем, что на сегодняшний день объемы хранимых данных становятся слишком большими для того, чтобы была возможность обрабатывать их традиционными алгоритмами. Технология MapReduce позволяет производить эффективные распределенные вычисления за оптимальное время выполнения.
К тому же, технология MapReduce быстро развивается и распространяется. Многие компании используют ее для обработки данных, потому что она имеет открытый исходный код, масштабируема и не требует больших затрат на оборудование.
Новизна исследования состоит в том, что многие проблемы, возникающие, при обработке больших данных могут быть решены за счет высокой отказоустойчивости, масштабируемости и доступности технологии MapReduce.
Целью бакалаврской работы является разработка алгоритма построения инвертированного индекса на основе технологии MapReduce.
Для достижения поставленной цели необходимо выполнить следующие задачи:
1. Рассмотреть принципы работы различных алгоритмов построения инвертированного индекса, а также принцип работы парадигмы Mapreduce.
2. Сравнить существующие технологии для работы с большими данными.
3. Проанализировать результаты сравнения и выбрать наиболее эффективный способ реализации программы.
4. Проектирование программы.
5. Разработка программы
В первой главе рассматриваются алгоритмы построения инвертированного индекса и принцип работы технологии Mapreduce.
Во второй главе произведено сравнение и анализ технологий для работы с большими данными.
В третьей главе представлены проектирование и разработка алгоритма построения инвертированного индекса на основе модели MapReduce.
В заключении сформированы выводы, полученные в процессе выполнения бакалаврской работы.
Целью бакалаврской работы являлась разработка алгоритма построения инвертированного индекса на основе технологии MapReduce. Создание данного алгоритма позволяет распределено строить инвертированный индекс для большого набора документов, который в дальнейшем может быть использован для полнотекстового поиска.
Были рассмотрены теоретические аспекты и методы построения инвертированного индекса. Проведено сравнение технологий распределенных вычислений и установлено, что MapReduce является наиболее подходящей для данной задачи.
Был разработан алгоритм построения инвертированного индекса на основе технологии MapReduce, учитывающий частоту появления слова в каждом документе и обработку стоп-слов.
Было произведено сравнения времени последовательной программы и программы на основе Mapreduce. Результат эксперимента показал, что реализация, использующая парадигму MapReduce является эффективнее.
В дальнейшем инвертированный индекс можно использовать для поиска по текстам.
