- Перспектива структуры данных для априорного алгоритма на основе RDD в Spark (arXiv)
Автор: Панкадж Сингх, Судхакар Сингх, П. К. Мишра, Ракхи Гарг
Аннотация: В последние годы многие исследователи предложили ряд эффективных и масштабируемых алгоритмов анализа частых наборов элементов для анализа больших данных. Первоначально были предложены основанные на MapReduce алгоритмы добычи частых наборов элементов на кластере Hadoop. Хотя Hadoop был разработан как кластерная вычислительная система для обработки и обработки больших данных, но производительность Hadoop не соответствует ожиданиям для итеративных алгоритмов интеллектуального анализа данных из-за его высокой скорости ввода-вывода и записи, а затем чтения промежуточных данных. результат на диске. Следовательно, Spark был разработан как еще одна инфраструктура кластерных вычислений, которая намного быстрее, чем Hadoop, благодаря вычислениям в памяти. Он отлично подходит для итерационных алгоритмов и поддерживает пакетную, интерактивную, итеративную и потоковую обработку данных. Многие алгоритмы добычи частых наборов элементов были переработаны в Spark, и большинство из них основаны на Apriori. Все эти априорные алгоритмы на основе Spark используют Hash Tree в качестве базовой структуры данных. В этой статье исследуется эффективность различных структур данных для Apriori на основе Spark. Хотя перспектива структуры данных исследовалась ранее, но для Apriori на основе MapReduce, ее необходимо повторно исследовать в распределенной вычислительной среде Spark. Рассмотренными базовыми структурами данных являются Hash Tree, Trie и Trie Hash Table. Результаты экспериментов с эталонными наборами данных показывают, что производительность Apriori на основе Spark с Trie и Hash Table Trie почти одинакова, но оба работают во много раз лучше, чем Hash Tree в распределенной вычислительной среде Spark.
2. Оптимизация производительности априорного алгоритма на основе MapReduce в кластере Hadoop (arXiv)
Автор: Судхакар Сингх, Ракхи Гарг, П.К. Мишра.
Аннотация. Было предложено множество методов для реализации алгоритма Apriori в среде MapReduce, но лишь немногие из них направлены на повышение производительности. Алгоритмы FPC (комбинированный подсчет фиксированных проходов) и DPC (комбинированный подсчет динамических проходов) объединяют несколько проходов Apriori в одну фазу MapReduce для сокращения времени выполнения. В этой статье мы предлагаем улучшенные априорные алгоритмы на основе MapReduce VFPC (комбинированный подсчет фиксированных проходов на основе переменного размера) и ETDPC (комбинированный подсчет динамических проходов на основе прошедшего времени) по сравнению с FPC и DPC. Кроме того, мы оптимизируем многопроходные фазы этих алгоритмов, пропуская этап сокращения в некоторых проходах, и предлагаем алгоритмы Optimized-VFPC и Optimized-ETDPC. Количественный анализ показывает, что стоимость подсчета дополнительных необрезанных кандидатов, созданных из-за пропущенной обрезки, менее значительна, чем снижение стоимости вычислений из-за того же. Экспериментальные результаты показывают, что VFPC и ETDPC более надежны и гибки, чем FPC и DPC, тогда как их оптимизированные версии более эффективны с точки зрения времени выполнения.
