Mi comprensión es calcular percentiles, los datos deben ser ordenados. ¿Sería posible con una gran cantidad de datos repartidos en varios servidores, sin moverlo?¿Se pueden calcular los percentiles de un conjunto de datos de forma cartográfica?
La respuesta a su pregunta es sí, es posible. Pero Map-Reduce realmente no está diseñado para este tipo de tarea. Map-Reduce (como se usa en un clúster Hadoop, por ejemplo) brilla en datos no estructurados o semiestructurados. Si bien tiene la capacidad para procesar otros tipos, no es la más adecuada. (Tenía un proyecto en una empresa donde querían analizar XML en un clúster de Hadoop ... no era lo más divertido).
This scholarly article describe algunos de los problemas con Map-Reduce en datos estructurados y ofertas un enfoque alternativo con "Clydesdale". (Nunca he escuchado o usado esto, así que no puedo respaldarlo ni hablar sobre sus fortalezas/debilidades.)
Estoy buscando más enlaces que ofrezcan explicaciones y alternativas.
Si bien MapReduce como paradigma no parece adecuado para el problema, la implementación de hadoop de MR - es.
La implementación de Hadoop de map reduce se basa en ordenación distribuida - y es lo que necesita. Hadoop está haciendo la clasificación moviendo datos entre servidores solo una vez, no tan mal.
Sugiero que veas la implementación de hadoop terasort que ilustra la buena (y probablemente la mejor) forma de ordenar datos masivos con hadoop. http://hadoop.apache.org/docs/current/api/org/apache/hadoop/examples/terasort/package-summary.html
Primero crearía un histograma, ya sea en una máquina o varias máquinas. Una vez que tenga un recuento para cada valor posible de cubos con valores posibles, puede combinarlos si es necesario. La ganancia para usar un histograma es que tiene O (1) tiempo de inserción/ordenación en lugar de O (log n) y usa el espacio O (M) donde M es el número de valores posibles o segmentos en lugar de O (N) donde N es el numero de muestra
Un histograma se ordena de forma natural para que pueda obtener un recuento total y encontrar los percentiles contando desde cualquier extremo.