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

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

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

Журнал: Вестник Южно-Уральского государственного университета. Серия: Вычислительная математика и информатика @vestnik-susu-cmi

Статья в выпуске: 1 т.8, 2019 года.

Бесплатный доступ

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

Еще

Интеллектуальный анализ данных, поиск ассоциативных правил

Короткий адрес: https://sciup.org/147233191

IDR: 147233191   |   DOI: 10.14529/cmse190104

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

  • Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. СПб.: БХВ-Петербург, 2002. 608 с.
  • 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. P. 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. P. 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, P. 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. P. 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. P. 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. P. 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. P. 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. P. 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. P. 1-12.
  • DOI: 10.1145/342009.335372
  • IBM Quest Synthetic Data Generator. URL: https://ibmquestdatagen.sourceforge.io/(дата обращения: 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. P. 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. P. 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. P. 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. P. 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. P. 78-85.
  • Paranjape-Voditel P., Deshpande U. A DIC-based Distributed Algorithm for Frequent Itemset Generation//Journal of Software. 2011. Vol. 6, No. 2. P. 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. P. 96:1-96:7.
  • DOI: 10.1186/s12911-017-0496-3
  • Schlegel B., Karnagel T., Kiefer T., Lehner W. Scalable Frequent Itemset Mining on Many-core Processors//Proceedings of the 9th International Workshop on Data Management on New Hardware, DaMoN 2013, New York, NY, USA, June 24, 2013. 2013. P. 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. P. 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. P. 1575-1580. 1.
  • DOI: 10.23919/MIPRO.2017.797363
Еще
Статья научная
SciUp 2024 © 2024 ©