Параллельный поиск частых наборов на многоядерных ускорителях Intel MIC

Аннотация

Поиск ассоциативных правил предполагает нахождение устойчивых корреляций между наборами элементов в больших базах транзакционных данных и является одной из основных задач интеллектуального анализа данных. Ассоциативные правила генерируются на основе множества всех наборов, в которых элементы часто встречаются совместно. Алгоритм DIC (Dynamic Itemset Counting) является модификацией классического алгоритма Apriori поиска частых наборов. В отличие от предшественника DIC пытается сократить количество проходов по базе транзакций и сохранить при этом относительно небольшое количество наборов, поддержка которых подсчитывается в рамках одного прохода. В статье  рассмотрена проблема ускорения алгоритма DIC на многоядерной архитектуре Intel Many Integrated Core (MIC) для случая, когда база транзакций помещается в оперативную память. Разработанная с помощью технологии OpenMP параллельная реализация алгоритма DIC использует битовое представление транзакций и наборов, что позволяет ускорить и векторизовать подсчет поддержки наборов, реализуемый  посредством логических побитовых операций. Проведенные эксперименты с синтетическими и реальными данными подтвердили хорошую производительность и масштабируемость предложенного алгоритма.