rename latex --> communication
[ppam-mpi.git] / communication / short_paper / JDS2014_short2.tex
CommitLineData
81923e5c
BA
1\documentclass[12pt]{article}\r
2%\r
3%\r
4% Retirez le caractere "%" au debut de la ligne ci--dessous si votre\r
5% editeur de texte utilise des caracteres accentues\r
6%\usepackage[latin1]{inputenc}\r
7\usepackage[utf8]{inputenc}\r
8\r
9%\r
10% Retirez le caractere "%" au debut des lignes ci--dessous si vous\r
11% utiisez les symboles et macros de l'AMS\r
12\usepackage{amsmath}\r
13\usepackage{amsfonts}\r
14%\r
15%\r
16\setlength{\textwidth}{16cm}\r
17\setlength{\textheight}{21cm}\r
18\setlength{\hoffset}{-1.4cm}\r
19\r
20% for figures and tables\r
21\usepackage{float}\r
22\usepackage{graphicx}\r
23\usepackage{wrapfig}\r
24\usepackage{xcolor}\r
25\usepackage{hyperref}\r
26\hypersetup{\r
27 colorlinks,\r
28 linkcolor=black,\r
29 urlcolor=violet\r
30}\r
31\usepackage{scrextend}\r
32\usepackage{booktabs}\r
33%\r
34%\r
35\begin{document}\r
36\r
37%--------------------------------------------------------------------------\r
38\r
39\begin{center}\r
40{\Large\r
41 {\sc Parallélisation de l'algorithme des $k$-médoïdes. Application au clustering de courbes.} %heuristique ?!\r
42}\r
43\bigskip\r
44\r
45Benjamin Auder $^{1}$ \& Jairo Cugliari $^{2}$\r
46\bigskip\r
47\r
48{\it\r
49$^{1}$ Laboratoire LMO. Université Paris-Sud. Bât 425. 91405 Orsay Cedex, France.\\benjamin.auder@math.u-psud.fr\r
50\r
51$^{2}$ Laboratoire ERIC. Université Lumière Lyon 2. Bât K. 69676 Bron Cedex, France.\\jairo.cugliari@univ-lyon2.fr\r
52}\r
53\end{center}\r
54\bigskip\r
55\r
56%--------------------------------------------------------------------------\r
57\r
58{\bf R\'esum\'e.} \r
59Nous présentons une méthode de clustering adaptée à de grandes bases de données de courbes densément discrétisées, donc elle-mêmes en grande dimension. \r
60La classification obtenue peut être utilisée afin de choisir de meilleurs modèles de prédiction de courbes, plus spécifiques, dans chacun des groupes. \r
61La méthode consiste en deux principales étapes : \r
62réduire la dimension des courbes via une base d'ondelettes, puis effectuer le clustering en parallèle. \r
63Les ondelettes sont bien adaptées pour identifier des caractéristiques localisées en temps et échelle. \r
64De plus, l'aspect multi-résolution de la transformée en ondelettes permet de regrouper les coefficients \r
65selon leur contribution à l'énergie totale, fournissant ainsi des représentants compacts pour chaque courbe. \r
66L'algorithme des $k$-médoïdes est appliqué à plusieurs sous-échantillons de l'ensemble des représentations réduites, \r
67puis les centres finaux sont obtenus en recherchant la médiane (ou éventuellement la moyenne) des médoïdes des échantillons. \r
68Des applications sont présentées sur deux jeux de données, dont les consommations électriques irlandaises journalières.\r
69\smallskip\r
70\r
71{\bf Mots-cl\'es.} réduction de dimension, ondelettes, $k$-médoïdes, parallèle\r
72\bigskip\bigskip\r
73\r
74{\bf Abstract.}\r
75We present a clustering method adapted to large databases of densely sampled curves, hence themselves in high dimension. \r
76The resulting classification can help to better tune models to predict new curves, each in every group. \r
77The method consists of two main steps: \r
78use a wavelet basis to reduce curves dimensionality, and then run a parallel clustering algorithm. \r
79Wavelets are well suited to identify characteristics localized both in time and space. \r
80Moreover, the multiresolution nature of the wavelets transform allows to group coefficients according to their \r
81contribution to the total energy, thus providing compact representations for every curve. \r
82The $k$-medoids algorithm is applied to several subsamples of all the reduced representations, and then the final \r
83centers are obtained by computing the median (or mean) of the samples medoids. \r
84Applications are shown on two databases, including Irish daily electrical consumptions.\r
85\smallskip\r
86\r
87{\bf Keywords.} dimensionality reduction, wavelets, $k$-medoids, parallel\r
88\r
89%~ Nous présentons une méthode de clustering adaptée à de grandes bases de données de courbes densément discrétisées, donc elle-mêmes en grande dimension. La classification obtenue peut être utilisée afin de choisir de meilleurs modèles de prédiction de courbes, plus spécifiques, dans chacun des groupes. La méthode consiste en deux principales étapes : réduire la dimension des courbes via une base d'ondelettes, puis effectuer le clustering en parallèle. Les ondelettes sont bien adaptées pour identifier des caractéristiques localisées en temps et échelle. De plus, l'aspect multi-résolution de la transformée en ondelettes permet de regrouper les coefficients selon leur contribution à l'énergie totale, fournissant ainsi des représentants compacts pour chaque courbe. L'algorithme des k-médoïdes est appliqué à plusieurs sous-échantillons de l'ensemble des représentations réduites, puis les centres finaux sont obtenus en recherchant la médiane (ou éventuellement la moyenne) des médoïdes des échantillons. Des applications sont présentées sur deux jeux de données, dont les consommations électriques irlandaises journalières.\r
90\r
91%--------------------------------------------------------------------------\r
92\r
93\section{Introduction}\r
94\r
95% * clustering\r
96% * parallelisation of clustering\r
97% * fda + wavelets\r
98% * données individuelles de conso\r
99\r
100Récemment, le contexte du \textit{Big Data} a rendu nécessaire le développement d'algorithmes spécifiques à de (très) \r
101grands volumes de données, éventuellement aussi en grande dimension comme c'est le cas dans notre étude. \r
102Ainsi ont vu le jour des algorithmes opérant sur de grands graphes (Kang et al.~2009) ou sur des flux de données haut débit (De Francisci Morales et Bifet~2013), entre entres. \r
103Le livre de Bekkerman et al.~(2011) présente des algorithmes de Machine Learning s'exécutant en parallèle sur diverses architectures, et \r
104ce type de programmation est en plein essor.\\\r
105\r
106\noindent La classification non supervisée (\textit{clustering}) est une des branches de l'apprentissage non supervisé. \r
107L'objectif est de regrouper les données en \textit{clusters} homogènes, suffisamment distincts deux à deux. \r
108Depuis la proposition originale de Tyron~(1939) un grand nombre d'articles ont été publié à ce sujet (voir Berkhin~2006 pour une revue). \r
109Cependant, il n'y a pas de consensus sur la définition d'un cluster : celle-ci varie en fonction des données, du contexte et de l'algorithme utilisé. \r
110Malgré ce fait, la classification non supervisée reste une technique très populaire qui permet \r
111de réduire la taille des données en les résumant à quelques représentants ; c'est particulièrement intéressant lorsqu'on travaille sur de grosses bases de données.\\\r
112\r
113\noindent Dans ce travail nous avons choisi d'adapter un algorithme de clustering classique pour une exécution parallèle, opérant sur des données de dimension réduite. \r
114La première partie présente la technique retenue afin d'abaisser la dimension via une base d'ondelettes. \r
115L'algorithme classant les données en parallèle est expliqué dans la seconde partie, puis nous montrons quelques résultats de tests.\r
116\r
117\section{Réduction de dimension}\r
118\r
119Dans cette section nous expliquons comment sont traitées les variables fonctionnelles (voir Antoniadis et al.~(2013) pour plus de détails).\\\r
120\r
121\noindent Chaque fonction $z$ est d'abord discrétisée sur une fine grille (toutes les 30 minutes pour les consommations électriques), et \r
122la discrétisation est encore notée $z = \{ z(t_i), i = 1, \ldots, N \}$. \r
123$z$ est alors approchée (jusqu'à l'échelle $J$) par un développement tronqué sur une base d'ondelettes avec un coefficient d'échelle $c_{0,0}$ \r
124et les coefficients d'ondelettes $\{d_{j, k}\}_{j, k}$ :\r
125%\r
126\begin{equation} \label{approx}\r
127 z_J(t) = c_{0,0} \phi_{0, 0} (t) + \sum_{j=0}^{J-1} \sum_{k=0}^{2^j - 1} d_{j,k} \psi_{j, k} (t).\r
128\end{equation}\r
129Alors, l'énergie $\mathcal{E}_Z = \| z \|^2_{ L_2 }$ de chaque fonction $z$ est égale à la somme des énergies \r
130de ses coefficients en ondelettes distribuées à travers les échelles :\r
131%\r
132\begin{equation} \label{scaledist}\r
133 \mathcal{E}_z \approx c_{0,0}^2 + \sum_{j=0}^{J-1} \| \mathbf{W}_j \|^2_2,\r
134\end{equation}\r
135%\r
136où $\| \mathbf{W}_j \|^2_2 = (d_{j, 0}, \ldots d_{j, 2^j - 1})'$, l'approximation étant due à la troncature à l'échelle $J$. \r
137On ne s'intéresse qu'à l'information contenue dans la forme des fonctions, pas à celle de son niveau moyen. \r
138Ainsi, on définit la contribution absolue de l'échelle $j$ à l'énergie globale de la fonction centrée comme\r
139 \[ \hbox{cont}_j = \| \mathbf{W}_j \|^2_2, \qquad j=0,\ldots,J-1. \]\r
140Finalement, chaque fonction est caractérisée par le vecteur de ses contributions absolues à l'énergie globale.\\\r
141\r
142\noindent En pratique nous choisissons $J$ de l'ordre de $\log_2(N)$ : c'est la valeur maximale possible compte-tenu de la discrétisation.\r
143\r
144\section{$k$-médoïdes parallèle}\r
145\r
146Nous rappelons tout d'abord l'algorithme des $k$-médoïdes, puis indiquons comment s'est déroulée la parallélisation.\\\r
147\r
148%\subsection{Algorithme des $k$-médoïdes}\r
149\noindent \textbf{Algorithme des $k$-médoïdes}\\\r
150Comme dans l'algorithme des $k$-means, l'idée est de partitionner les données autour de $k$ centres, ici appelés \emph{médoïdes}. \r
151La fonction à minimiser (\emph{distorsion}) est similaire :\r
152$$D(x) = \min_{m_1,\dots,m_k \in \mathbb{R}^d} \sum_{i=1}^{n} \min_{j=1,\dots,k} \| x_i - m_j \| \, ,$$\r
153avec $x = (x_1,\dots,x_n)$, $\|\,.\,\|$ pouvant désigner n'importe quelle norme ; ici nous choisissons la norme euclidienne. \r
154Les distances n'apparaissant pas au carré, cet algorithme est moins sensible aux outliers que le $k$-means. \r
155Cependant, sa programmation est plus délicate car dans le cas de la médiane spatiale il n'existe pas de formule analogue à celle de la moyenne. \r
156La première implémentation de l'algorithme est celle de Kaufman et Rousseeuw~(1987), PAM pour Partitioning Around Medoids. \r
157Elle est assez coûteuse, mais donne de bons résultats et reste simple à écrire. Diverses heuristiques ou accélérations autour de cette implémentation \r
158ont été développés (voir Chu et al.~2002 par exemple), mais nous utilisons ici la version originale, qui se révèle suffisante.\\\r
159%TODO: encadré algo PAM. [si reste de la place...]\r
160\r
161%\subsection{Parallélisation avec MPI}\r
162\noindent \textbf{Parallélisation avec MPI}\\\r
163MPI est une librarie permettant de faciliter l'écriture de programmes en parallèle. \r
164%Elle est disponible pour divers langages dont le C, que nous avons choisi. \r
165%~ Son principe est le suivant :\r
166%~ \begin{enumerate}\r
167%~ \item un certain nombre de coeurs de calcul sont alloués et initialisés avec les mêmes valeurs sauf une : le rang du processus ;\r
168%~ \item chaque coeur exécute séquentiellement deux types d'instructions : locales, comme dans un programme normal, \r
169%~ et de communication, où il envoie un ou plusieurs message à un ou plusieurs autres processus. Ces messages peuvent demander ou envoyer des résultats, mais aussi \r
170%~ effectuer des actions plus élaborées comme [TODO]\r
171%~ \item le calcul se termine lorsque tous les coeurs sont arrêtés.\r
172%~ \end{enumerate}\r
173Nous l'utilisons en mode master-slave, c'est à dire que le travail est divisé en deux types d'entités: un processus coordinateur, \r
174et des coeurs se contentant d'exécuter les demandes du processus maître. \r
175%~ \begin{itemize}\r
176%~ \item master : reçoit l'entrée initiale, coordonne les autres processus pour effectuer la tâche, et rassemble les résultats ;\r
177%~ \item slave : boucle en attendant des instructions du processus maître, exécute les sous-tâches et retourne les résultats partiels.\r
178%~ \end{itemize}\r
179Voici le flot d'exécution du programme final :\\\r
180%\begin{enumerate}\r
181\begin{addmargin}[1em]{2em}% 1em left, 2em right\r
182\noindent \textbf{1.} le processus maître découpe le problème en sous-tâches sur des jeux de données plus petits, et les envoie à chaque esclave ;\\\r
183\textbf{2.} pour une sous-tâche donnée, on réduit la dimension puis applique l'algorithme de clustering, et retourne les centres ;\\\r
184\textbf{3.} le processus principal récupère et aggrège les résultats en un jeu de $k$ centres.\\\r
185\end{addmargin}\r
186%\end{enumerate}\r
187Le code sera disponible prochainement sur \href{https://github.com/}{github}.\r
188%TODO: code disponible en ligne sur github. (faut beautifier quelques bricoles dans le code d'abord, en particulier serialize/deserialize et type d'ondelette en argument (?!)\r
189\r
190\section{Applications}\r
191\r
192Deux jeux de données ont été utilisés ici : des évolutions de magnitudes d'étoiles, et de consommations électriques de clients individuels.\r
193\r
194\subsection{Magnitudes d'étoiles}\r
195\r
196Ce jeu de données récupéré via le site web de Keogh et al.~(2011) consiste en un ensemble d'entraînement de 1000 courbes, \r
197et une base de test de 8236 courbes. Chacune d'entre elle a un label compris entre 1 et 3 ; la figure \ref{figsltr3clusts} les représente. \r
198On remarque que les groupes 1 et 3 sont assez similaires, contenant des courbes difficiles à classer.\r
199\r
200\begin{figure}[H]\r
201\begin{minipage}[c]{.32\linewidth}\r
202 \includegraphics[width=5cm,height=3.5cm]{img/slgr1.png}\r
203 \vspace*{-0.3cm}\r
204 \caption{Groupe 1}\r
205\end{minipage}\r
206\begin{minipage}[c]{.32\linewidth}\r
207 \includegraphics[width=5cm,height=3.5cm]{img/slgr2.png}\r
208 \vspace*{-0.3cm}\r
209 \caption{Groupe 2}\r
210\end{minipage}\r
211\begin{minipage}[c]{.32\linewidth}\r
212 \includegraphics[width=5cm,height=3.5cm]{img/slgr3.png}\r
213 \vspace*{-0.3cm}\r
214 \caption{Groupe 3}\r
215\end{minipage}\r
216\label{figsltr3clusts}\r
217\end{figure}\r
218\r
219Compte-tenu du relatif faible nombre d'échantillons nous pouvons lancer le programme sur tout le jeu de données ; \r
220cela permet de comparer aux résultats obtenus par la version parallèle, que l'on espère presque aussi bons. \r
221Le tableau \ref{tabDistorSl} contient les distorsions empiriques calculées sur les ensemble d'entraînement et de test, \r
222ainsi que l'adéquation des deux partitions ("intra"), et leur adéquation à la partition réelle ("inter"). Cette dernière est mauvaise à cause de la remarque précitée :\r
223les courbes des clusters 1 et 3 se ressemblent trop pour appliquer un algorithme de partitionnement de type $k$-means.\\\r
224\r
225\begin{table}[H]\r
226\centering\r
227\begin{tabular}{lccc}\r
228\toprule\r
229 & & \multicolumn{2}{c}{Adéquation} \\\r
230 & Distorsion & Intra & Inter \\\r
231\midrule\r
232Entraînement séquentielle. & 1.31e4 & 0.79 & 0.77\\\r
233%\hline\r
234Entraînement parallèle & 1.40e4 & 0.79 & 0.68\\\r
235%\hline\r
236Test séquentielle & 1.09e5 & 0.78 & 0.76\\\r
237%\hline\r
238Test parallèle & 1.15e5 & 0.78 & 0.69\\\r
239\bottomrule\r
240\end{tabular}\r
241\caption{Distorsions et indices d'adéquation des partitions}\r
242\label{tabDistorSl}\r
243\end{table}\r
244\r
245% \begin{table}[H]\r
246% \centering\r
247% \begin{tabular}{|l|c|c|c|}\r
248% \hline\r
249% & Distorsion & "Intra-adéquation" & "Inter-adéquation" \\\r
250% \hline\r
251% Entraînement seq. & 1.31e4 & 0.79 & 0.77\\\r
252% \hline\r
253% Entraînement // & 1.40e4 & 0.79 & 0.68\\\r
254% \hline\r
255% Test seq. & 1.09e5 & 0.78 & 0.76\\\r
256% \hline\r
257% Test // & 1.15e5 & 0.78 & 0.69\\\r
258% \hline\r
259% \end{tabular}\r
260% \caption{Distorsions et indices d'adéquation des partitions}\r
261% \label{tabDistorSl}\r
262% \end{table}\r
263\r
264%~ 1) Starlight curves : utiliser 1000 (resp. 3000) courbes pour le clustering, puis ~9000 (resp. ~7000) pour classif.\r
265%~ Comparer les médoïdes (renuméroter en sortie du code), et afficher les perfs : taux de classif correcte.\r
266\r
267\subsection{Consommations électriques irlandaises}\r
268\r
269Nous utilisons les données de consommation d'électricité de foyers irlandais (Electricity Smart Meter CBT) de l'ISSDA\footnote{\textit{Irish Social Science Data Archive}, \url{http://www.ucd.ie/issda/data/}.}. Après nettoyage des données manquantes, ce jeu de données consiste en 4621 séries temporelles représentant l'évolution de la consommation électrique d'autant de foyers irlandais. \r
270%Celles-ci sont similaires aux courbes EDF sur lesquelles vise à être appliquée notre méthode. \r
271Nous avons choisi d'appliquer l'algorithme avec 3 et 5 classes. Compte-tenu du grand nombre de points de discrétisation (25k) \r
272et de la haute variabilité des données, celles-ci sont difficiles à représenter. Ainsi nous n'indiquons que les résultats numériques ; \r
273ils sont visibles dans le tableau \ref{tabDistorIr}, et sont cette fois plutôt bons.\\\r
274\r
275\begin{table}[H]\r
276\centering\r
277\begin{tabular}{lcc} \toprule\r
278%\hline\r
279 & & Intra-adéquation \\\r
280 & Distorsion & séquentielle vs parallèle \\ \r
281\midrule %\hline\r
2823 clusters séquentielle & 1.90e7 & 0.90\\\r
283%\hline\r
2843 clusters parallèle & 2.15e7 & 0.90\\\r
285%\hline\r
2865 clusters séquentielle & 1.61e7 & 0.89\\\r
287%\hline\r
2885 clusters parallèle & 1.84e7 & 0.89\\\r
289\bottomrule %\hline \r
290\end{tabular}\r
291\caption{Distorsions et indices d'adéquation des partitions}\r
292\label{tabDistorIr}\r
293\end{table}\r
294%pour un nombre de clusters égal à 3, 7 et 15.\r
295\r
296\section{Conclusion}\r
297\r
298Nous avons cherché à identifier des groupes de consommateurs à partir de données fonctionnelles \r
299pour bénéficier de l'information supplémentaire fournie par la forme des courbes, qui serait perdue \r
300si on les considérait comme de simples vecteurs. Cette forme est capturée $-$ entre autres caractéristiques $-$ \r
301par les coefficients d'ondelettes, regroupés par niveaux d'énergie. Les dissimilarités sont calculées ensuite \r
302via une distance $L^p$. Alternativement (ou complémentairement), il serait intéressant d'utiliser une mesure de dissimilarité \r
303plus directement basée sur la forme des courbes, comme le font Antoniadis et al.~(2013) ou Heckman et Zamar~(2000).\r
304\r
305Ensuite, la procédure de clustering mise en place est prévue pour passer à l'échelle. Initialement conçue pour être appliquée sur un jeu de données de plusieurs dizaines de millions de courbes, elle pourrait être appliquée à l'ensemble de clients d'un pays. Les résultats obtenus sur les deux jeux de données présentés sont assez encourageants, et permettent d'envisager une utilisation à plus grande échelle.\r
306\r
307%~ \section{Exemple de r\'ef\'erences bibliographiques}\r
308%~ La n\'ecessit\'e de produire des r\'esum\'es clairs et bien\r
309%~ r\'ef\'erenc\'es a \'et\'e d\'emontr\'ee par Achin et Quidont~(2000).\r
310%~ Le r\'ecent article de Noteur~(2003) met en \'evidence \dots\r
311\r
312%Quelques rappels :\r
313%%\r
314%\begin{center}\r
315%%\r
316%\begin{tabular}{lr} \hline\r
317%%\r
318%Accent aigu : & \'e; \\\r
319%Accent grave : & \`a;\\\r
320%Accent circonflexe : & \^o mais \^{\i};\\\r
321%Tr\'emas : & \"o mais \"{\i};\\\r
322%C\'edille : & \c{c}. \\ \hline\r
323%\end{tabular}\r
324%%\r
325%\end{center}\r
326\r
327%--------------------------------------------------------------------------\r
328\r
329\section*{Bibliographie}\r
330\r
331\noindent [1] A. Antoniadis, X. Brossat, J. Cugliari et J.-M. Poggi (2013), Clustering Functional Data Using Wavelets, {\it International Journal of Wavelets, Multiresolution and Information Processing}, 11(1), 35--64.\\\r
332\noindent [2] R. Bekkerman, M. Bilenko et J. Langford - éditeurs (2011), Scaling up Machine Learning: Parallel and Distributed Approaches, {\it Cambridge University Press}.\\\r
333\noindent [3] P. Berkhin (2006), A Survey of Clustering Data Mining Techniques, {\it Grouping Multidimensional Data, éditeurs : J. Kogan, C. Nicholas, M. Teboulle}.\\\r
334\noindent [4] S.-C. Chu, J.F. Roddick et J.S. Pan (2002), An Efficient K-Medoids-Based Algorithm Using Previous Medoid Index, Triangular Inequality Elimination Criteria, and Partial Distance Search, {\it Lecture Notes in Computer Science}, 2454, 63--72.\\\r
335\noindent [5] G. De Francisci Morales et A. Bifet (2013), G. De Francisci Morales SAMOA: A Platform for Mining Big Data Streams Keynote Talk at RAMSS ’13: 2nd International Workshop on Real-Time Analysis and Mining of Social Streams WWW, Rio De Janeiro.\\\r
336\noindent [6] N.E. Heckman et R.H. Zamar (2000), Comparing the shapes of regression functions. {\it Biometrika}, 87(1), 135--144.\\\r
337\noindent [7] U. Kang, C.E. Tsourakakis et C. Faloutsos (2009), PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations, {\it IEEE International Conference on Data Mining}.\\\r
338\noindent [8] L. Kaufman et P.J. Rousseeuw (1987), Clustering by means of Medoids, {\it Statistical Data Analysis Based on the L\_1-Norm and Related Methods, éditeur : Y. Dodge}.\\\r
339\noindent [9] E. Keogh, Q. Zhu, B. Hu, Y. Hao, X. Xi, L. Wei et C.A. Ratanamahatana (2011), The UCR Time Series Classification/Clustering, \url{ www.cs.ucr.edu/\~eamonn/time\_series\_data/}.\\\r
340\noindent [10] R.C. Tryon (1939), Cluster analysis. {\it New York: McGraw Hill}.\\\r
341\r
342\r
343\r
344\end{document}\r
345\r
346\r
347\r
348%\noindent [7] C.C. Aggarwal - éditeur (2006) Data Streams: Models and Algorithms, \{it Advances in Database Systems}.\r
349%[Pegasus: Mining billion-scale graphs in the cloud ? mars 2012, mais 4 pages...]\r
350%Data Warehousing and Knowledge Discovery. \r
351\r
352%\noindent [4] F. Chang, J. Dean, S. Ghemawat, W.C. Hsieh, D.A. Wallach, M. Burrows, T. Chandra, A. Fikes, et R.E. Gruber (2006), Bigtable: A Distributed Storage System for Structured Data, {\it Seventh Symposium on Operating System Design and Implementation}.\\\r
353\r
354%\noindent [6] J. Dean et S. Ghemawat (2004), MapReduce: Simplified Data Processing on Large Clusters, {\it Sixth Symposium on Operating System Design and Implementation}.\\\r