Mein Verständnis ist Perzentilen zu berechnen, müssen die Daten sortiert werden. Wäre dies mit einer großen Menge an Daten möglich, die auf mehrere Server verteilt sind, ohne sie zu verschieben?Können Perzentile eines Datensatzes auf eine Map-Reduced-Art berechnet werden?
Die Antwort auf Ihre Frage ist ja, es ist möglich. Aber Map-Reduce ist nicht wirklich für diese Aufgabe geeignet. Map-Reduce (wie es beispielsweise in einem Hadoop-Cluster verwendet wird) scheint auf unstrukturierte oder halbstrukturierte Daten. Während es die Fähigkeit hat, andere Arten zu verarbeiten, ist es nicht für es am besten geeignet. (Ich hatte ein Projekt in einem Unternehmen, wo XML in einem Hadoop-Cluster analysiert werden sollte ... es war nicht die meiste Spaß.)
beschreibt einige der Probleme mit Map-Reduce auf strukturierte Daten und Angebote ein alternativer Ansatz mit "Clydesdale". (Ich habe noch nie davon gehört oder dies verwendet, daher kann ich es weder befürworten noch seine Stärken/Schwächen ansprechen.)
Ich bin auf der Suche nach mehr Links, die Erklärungen und Alternativen bieten.
Während MapReduce als Paradigma für das Problem nicht geeignet erscheint, ist die Implementierung von MR - von hadoop.
Die Implementierung von Hadoop Map reduzieren basiert auf verteilte Sortierung - und es ist, was Sie brauchen. Hadoop macht eine Sortierung, indem Daten zwischen Servern nur einmal verschoben werden - nicht so schlimm.
Ich würde vorschlagen, auf Hadoop-Implementierung zu sehen, die die gute (und wahrscheinlich die beste) Möglichkeit, massive Daten mit Hadoop zu sortieren, veranschaulichen. http://hadoop.apache.org/docs/current/api/org/apache/hadoop/examples/terasort/package-summary.html
Ich würde zuerst ein Histogramm erstellen, entweder auf einer Maschine oder mehreren Maschinen. Sobald Sie für jeden möglichen Wert von Buckets mit möglichen Werten eine Zählung haben, können Sie diese bei Bedarf kombinieren. Der Gewinn für die Verwendung eines Histogramms ist, dass es eine O (1) -Einfügungs-/Sortierzeit anstelle von O (log n) hat und O (M) -Raum verwendet, wobei M die Anzahl der möglichen Werte oder Buckets anstelle von O (N) ist ist die Anzahl der Proben.
Ein Histogramm wird natürlich sortiert, so dass Sie eine Gesamtanzahl erhalten und die Perzentile durch Zählen von jedem Ende finden können.