Published November 30, 2019
| Version v1
Publication
Open
On using MapReduce to scale algorithms for Big Data analytics: a case study
- 1. Naresuan University
- 2. Texas Tech University
Description
Abstract Introduction Many data analytics algorithms are originally designed for in-memory data. Parallel and distributed computing is a natural first remedy to scale these algorithms to "Big algorithms" for large-scale data. Advances in many Big Data analytics algorithms are contributed by MapReduce, a programming paradigm that enables parallel and distributed execution of massive data processing on large clusters of machines. Much research has focused on building efficient naive MapReduce-based algorithms or extending MapReduce mechanisms to enhance performance. However, we argue that these should not be the only research directions to pursue. We conjecture that when naive MapReduce-based solutions do not perform well, it could be because certain classes of algorithms are not amendable to MapReduce model and one should find a fundamentally different approach to a new MapReduce-based solution. Case description This paper investigates a case study of a scaling problem of "Big algorithms" for a popular association rule-mining algorithm, particularly the development of Apriori algorithm in MapReduce model. Discussion and evaluation Formal and empirical illustrations are explored to compare our proposed MapReduce-based Apriori algorithm with previous solutions. The findings support our conjecture and our study shows promising results compared to the state-of-the-art performer with 7% increase in performance on the average of transactions ranging from 10,000 to 120,000. Conclusions The results confirm that effective MapReduce implementation should avoid dependent iterations, such as that of the original sequential Apriori algorithm. These findings could lead to many more alternative non-naive MapReduce-based "Big algorithms".
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
مقدمة مجردة تم تصميم العديد من خوارزميات تحليل البيانات في الأصل للبيانات الموجودة في الذاكرة. الحوسبة المتوازية والموزعة هي العلاج الأول الطبيعي لتوسيع نطاق هذه الخوارزميات إلى "خوارزميات كبيرة" للبيانات واسعة النطاق. يساهم MapReduce في التقدم في العديد من خوارزميات تحليلات البيانات الضخمة، وهو نموذج برمجة يتيح التنفيذ المتوازي والموزع لمعالجة البيانات الضخمة على مجموعات كبيرة من الآلات. ركزت الكثير من الأبحاث على بناء خوارزميات فعالة قائمة على MapReduce أو توسيع آليات MapReduce لتعزيز الأداء. ومع ذلك، فإننا نجادل بأن هذه لا ينبغي أن تكون الاتجاهات البحثية الوحيدة التي يجب متابعتها. نعتقد أنه عندما لا تؤدي الحلول القائمة على MapReduce الساذجة أداءً جيدًا، فقد يكون ذلك بسبب أن فئات معينة من الخوارزميات غير قابلة للتعديل وفقًا لنموذج MapReduce ويجب على المرء إيجاد نهج مختلف جذريًا لحل جديد قائم على MapReduce. وصف الحالة تبحث هذه الورقة في دراسة حالة لمشكلة تحجيم "الخوارزميات الكبيرة" لخوارزمية تعدين قواعد الارتباط الشائعة، ولا سيما تطوير خوارزمية Apriori في نموذج MapReduce. المناقشة والتقييم يتم استكشاف الرسوم التوضيحية الرسمية والتجريبية لمقارنة خوارزمية Apriori المستندة إلى MapReduce المقترحة مع الحلول السابقة. تدعم النتائج تخميننا وتظهر دراستنا نتائج واعدة مقارنة بأحدث أداء مع زيادة بنسبة 7 ٪ في الأداء في متوسط المعاملات التي تتراوح من 10000 إلى 120،000. الاستنتاجات تؤكد النتائج أن تنفيذ MapReduce الفعال يجب أن يتجنب التكرارات التابعة، مثل خوارزمية Apriori المتسلسلة الأصلية. يمكن أن تؤدي هذه النتائج إلى العديد من "الخوارزميات الكبيرة" البديلة غير الساذجة القائمة على MapReduce.Translated Description (French)
Résumé Introduction De nombreux algorithmes d'analyse de données sont conçus à l'origine pour les données en mémoire. L'informatique parallèle et distribuée est un premier remède naturel pour adapter ces algorithmes aux « gros algorithmes » pour les données à grande échelle. Les avancées dans de nombreux algorithmes d'analyse de Big Data sont apportées par MapReduce, un paradigme de programmation qui permet l'exécution parallèle et distribuée d'un traitement massif de données sur de grands groupes de machines. De nombreuses recherches se sont concentrées sur la création d'algorithmes naïfs efficaces basés sur MapReduce ou sur l'extension des mécanismes MapReduce pour améliorer les performances. Cependant, nous soutenons que celles-ci ne devraient pas être les seules orientations de recherche à suivre. Nous supposons que lorsque les solutions naïves basées sur MapReduce ne fonctionnent pas bien, cela pourrait être dû au fait que certaines classes d'algorithmes ne sont pas modifiables en modèle MapReduce et que l'on devrait trouver une approche fondamentalement différente d'une nouvelle solution basée sur MapReduce. Description du cas Cet article étudie une étude de cas d'un problème de mise à l'échelle de « grands algorithmes » pour un algorithme d'extraction de règles d'association populaire, en particulier le développement de l'algorithme Apriori dans le modèle MapReduce. Discussion et évaluation Des illustrations formelles et empiriques sont explorées pour comparer notre algorithme Apriori basé sur MapReduce proposé avec les solutions précédentes. Les résultats confirment notre hypothèse et notre étude montre des résultats prometteurs par rapport à l'artiste à la pointe de la technologie avec une augmentation de 7 % de la performance sur la moyenne des transactions allant de 10 000 à 120 000. Conclusions Les résultats confirment que la mise en œuvre efficace de MapReduce doit éviter les itérations dépendantes, telles que celles de l'algorithme Apriori séquentiel d'origine. Ces résultats pourraient conduire à de nombreux autres « grands algorithmes » non naïfs basés sur MapReduce.Translated Description (Spanish)
Resumen Introducción Muchos algoritmos de análisis de datos están diseñados originalmente para datos en memoria. La computación paralela y distribuida es un primer remedio natural para escalar estos algoritmos a "Grandes algoritmos" para datos a gran escala. Los avances en muchos algoritmos de análisis de Big Data son aportados por MapReduce, un paradigma de programación que permite la ejecución paralela y distribuida de procesamiento masivo de datos en grandes grupos de máquinas. Gran parte de la investigación se ha centrado en construir algoritmos ingenuos eficientes basados en MapReduce o en extender los mecanismos de MapReduce para mejorar el rendimiento. Sin embargo, argumentamos que estas no deberían ser las únicas direcciones de investigación a seguir. Conjeturamos que cuando las soluciones ingenuas basadas en MapReduce no funcionan bien, podría deberse a que ciertas clases de algoritmos no son modificables al modelo MapReduce y uno debería encontrar un enfoque fundamentalmente diferente para una nueva solución basada en MapReduce. Descripción del caso Este documento investiga un estudio de caso de un problema de escala de "Grandes algoritmos" para un algoritmo popular de minería de reglas de asociación, particularmente el desarrollo del algoritmo Apriori en el modelo MapReduce. Discusión y evaluación Se exploran ilustraciones formales y empíricas para comparar nuestro algoritmo Apriori basado en MapReduce propuesto con soluciones anteriores. Los hallazgos respaldan nuestra conjetura y nuestro estudio muestra resultados prometedores en comparación con el rendimiento de última generación con un aumento del 7% en el rendimiento en el promedio de transacciones que van desde 10.000 a 120.000. Conclusiones Los resultados confirman que la implementación efectiva de MapReduce debe evitar iteraciones dependientes, como la del algoritmo Apriori secuencial original. Estos hallazgos podrían conducir a muchos más "Grandes algoritmos" alternativos no ingenuos basados en MapReduce.Files
s40537-019-0269-1.pdf
Files
(1.9 MB)
| Name | Size | Download all |
|---|---|---|
|
md5:989c84f5400128f807bedb80fabaf75d
|
1.9 MB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- حول استخدام MapReduce لتوسيع نطاق الخوارزميات لتحليلات البيانات الضخمة: دراسة حالة
- Translated title (French)
- Sur l'utilisation de MapReduce pour faire évoluer les algorithmes d'analyse Big Data : une étude de cas
- Translated title (Spanish)
- Sobre el uso de MapReduce para escalar algoritmos para el análisis de Big Data: un estudio de caso
Identifiers
- Other
- https://openalex.org/W2991050497
- DOI
- 10.1186/s40537-019-0269-1
References
- https://openalex.org/W1823396250
- https://openalex.org/W1970282669
- https://openalex.org/W1981162575
- https://openalex.org/W1995797177
- https://openalex.org/W2001785976
- https://openalex.org/W2013344760
- https://openalex.org/W2017828380
- https://openalex.org/W2093456341
- https://openalex.org/W2129714679
- https://openalex.org/W2140838268
- https://openalex.org/W2144481322
- https://openalex.org/W2169541495
- https://openalex.org/W2173213060
- https://openalex.org/W2201122134
- https://openalex.org/W229682254
- https://openalex.org/W2329273625
- https://openalex.org/W2539869562
- https://openalex.org/W2559283969
- https://openalex.org/W2599592786
- https://openalex.org/W2748971311
- https://openalex.org/W2760494456
- https://openalex.org/W2765714237
- https://openalex.org/W2844620057
- https://openalex.org/W2883952940
- https://openalex.org/W2904236883
- https://openalex.org/W2956153389
- https://openalex.org/W2998574808
- https://openalex.org/W3133877534
- https://openalex.org/W4213146104
- https://openalex.org/W4253336088