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

Михаил Леонидович Цымблер

Аннотация


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

Ключевые слова


интеллектуальный анализ данных; поиск ассоциативных правил; OpenMP; Intel Many Integrated Core

Полный текст:

PDF

Литература


Voevodin V.V., Voevodin Vl.V. Parallellnye vachisleniya [Parallel Computing]. SPb: BHVPetersburg, 2002. 608 p.

Agrawal R., Srikant R. Fast Algorithms for Mining Association Rules in Large Databases. VLDB’94, Proceedings of 20th International Conference on Very Large Data Bases, September 12–15, 1994, Santiago de Chile, Chile. 1994. pp. 487–499.

Bacon D.F., Graham S.L., Sharp O.J. Compiler Transformations for High-Performance Computing. ACM Computing Surveys. 1994. vol. 26, no. 4. pp. 345–420. DOI: 10.1145/197405.197406.

Borgelt C. Frequent Item Set Mining. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. 2012. vol. 2, no. 6, pp. 437–456. DOI: 10.1002/widm.1074.

Brin S., Motwani R., Ullman J.D., Tsur S. Dynamic Itemset Counting and Implication Rules for Market Basket Data. SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13–15, 1997, Tucson, Arizona, USA. 1997. P. 255–264. DOI: 10.1145/253260.253325.

Burdick D., Calimlim M., Flannick J. et al. MAFIA: A Maximal Frequent Itemset Algorithm. IEEE Transactions on Knowledge and Data Engineering. 2005. vol. 17, no. 11. pp. 1490–1504. DOI: 10.1109/TKDE.2005.183.

Chang Y., Chen J., Tsai Y. Mining Subspace Clusters from DNA Microarray Data Using Large Itemset Techniques. Journal of Computational Biology. 2009. vol. 16, no. 5. pp. 745–768. DOI: 10.1089/cmb.2008.0161.

Cheung D.W., Hu K., Xia S. An Adaptive Algorithm for Mining Association Rules on Shared-Memory Parallel Machines. Distributed and Parallel Databases. 2001. vol. 9, no. 2. pp. 99–132. DOI: 10.1023/A:1018951022124.

Dong J., Han M. BitTableFI: An Efficient Mining Frequent Itemsets Algorithm. Knowledge-Based Systems. 2007. vol. 20, no. 4. pp. 329–335. DOI: j.knosys.2006.08.005.

Duran A., Klemm M. The Intel Many Integrated Core Architecture. 2012 International Conference on High Performance Computing and Simulation, HPCS 2012, Madrid, Spain, July 2–6, 2012. 2012. pp. 365–366. DOI: 10.1109/HPCSim.2012.6266938.

Han J., Pei J., Yin Y. Mining Frequent Patterns without Candidate Generation. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16–18, 2000, Dallas, Texas, USA. pp. 1–12. DOI: 10.1145/342009.335372.

IBM Quest Synthetic Data Generator. URL: https://ibmquestdatagen.sourceforge.io/ (accessed: 03.11.2018).

Kostenetskiy P., Safonov A. SUSU Supercomputer Resources. PCT’2016, International Scientific Conference on Parallel Computational Technologies, Arkhangelsk, Russia, March 29–31, 2016. CEUR Workshop Proceedings. vol. 1576, CEUR-WS.org, 2016. pp. 561–573.

Kumar P., Bhatt P., Choudhury R. Bitwise Dynamic Itemset Counting Algorithm. Proceedings of the ICCIC 2015, IEEE International Conference on Computational Intelligence and Computing Research, December 10–12, 2015, Madurai, India. 2015. pp. 1–4. DOI: 10.1109/ICCIC.2015.7435752.

Li J., Fu A.W., Fahey P. Efficient Discovery of Risk Patterns in Medical Data. Artificial Intelligence in Medicine. 2009. vol. 45, no. 1. pp. 77–89. DOI: 10.1016/j.artmed.2008.07.008.

Lischner R. STL Reference: Containers, Iterators, and Algorithms. O’Reilly, 2003. 120 p.

Ordonez C., Ezquerra N.F., Santana C.A. Constraining and Summarizing Association Rules in Medical Data. Knowledge and Information Systems. 2006. vol. 9, no. 3. pp. 1–2. DOI: 10.1007/s10115-005-0226-5.

Ordonez C., Santana C.A., de Braal L. Discovering Interesting Association Rules in Medical Data. 2000 ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, Dallas, Texas, USA, May 14, 2000. 2000. pp. 78–85.

Paranjape-Voditel P., Deshpande U. A DIC-based Distributed Algorithm for Frequent Itemset Generation. Journal of Software. 2011. vol. 6, no. 2. pp. 306–313. DOI: 10.4304/jsw.6.2.306-313.

Pattanaprateep O., McEvoy M., Attia J., Thakkinstian A. Evaluation of Rational Nonsteroidal Anti-inflammatory Drugs and Gastro-protective Agents Use; Association Rule Data Mining Using Outpatient Prescription Patterns. BMC Medical Informatics and Decision Making. 2017. vol. 17, no. 1. pp. 96:1–96:7. DOI: 10.1186/s12911-017-0496-3.

Schlegel B., Karnagel T., Kiefer T., Lehner W. Scalable Frequent Itemset Mining on Manycore Processors. Proceedings of the 9th International Workshop on Data Management on New Hardware, DaMoN 2013, New York, NY, USA, June 24, 2013. 2013. pp. 3. DOI: 10.1145/2485278.2485281.

Sokolinskaya I., Sokolinsky L. Revised Pursuit Algorithm for Solving Non-stationary Linear Programming Problems on Modern Computing Clusters with Manycore Accelerators. Supercomputing. RuSCDays 2016. Communications in Computer and Information Science. 2016. vol. 687. p. 212–223. DOI: 10.1007/978-3-319-55669-7_17.

Zaki M.J. Scalable Algorithms for Association Mining. IEEE Transactions on Knowledge and Data Engineering. 2000. vol. 12, no. 3. pp. 372–390. DOI: 10.1109/69.846291.

Zymbler M. Accelerating Dynamic Itemset Counting on Intel Many-core Systems. Proceedings of the 40th International Convention on Information and Communication Technology, Electronics and Microelectronics, MIPRO’2017, Opatija, Croatia, May 22–26, 2017. IEEE, 2017. pp. 1575–1580. DOI: 110.23919/MIPRO.2017.797363.




DOI: http://dx.doi.org/10.14529/cmse190104