Moje zrozumienie polega na obliczaniu percentyli, dane muszą być posortowane. Czy byłoby to możliwe dzięki dużej ilości danych rozłożonych na wielu serwerach, bez przenoszenia?Czy percentyle zbioru danych można obliczyć w sposób zmniejszający mapę?
Odpowiedź na pytanie to tak, jest to możliwe. Ale Map-Reduce nie jest specjalnie zaprojektowany do tego rodzaju zadań. Map-Reduce (na przykład w klastrze Hadoop) świeci na danych niestrukturalnych lub półstrukturalnych. Chociaż ma zdolność przetwarzania , nie nadaje się do tego najlepiej. (Miałem jeden projekt w firmie, w której chcieli analizować XML w klastrze Hadoop ... nie było to najfajniejsze.)
This scholarly article opisuje niektóre problemy związane z ograniczeniem mapy w przypadku danych strukturalnych i ofert alternatywne podejście z "Clydesdale". (Nigdy nie słyszałem o tym ani nie używałem tego, więc nie mogę go ani poprzeć, ani mówić do jego mocnych/słabych stron).
Szukam więcej linków, które oferują wyjaśnienia i alternatywy.
Podczas gdy MapReduce jako paradygmat nie wygląda najlepiej na problem, implementacja MR przez hadoop jest.
Implementacja redukcji map Hadoop jest oparta na sortowaniu rozproszonym - i to jest to, czego potrzebujesz. Hadoop robi sortowanie, przenosząc dane między serwerami tylko raz - nie tak źle.
Sugeruję, aby spojrzeć na wdrożenie teraort teraorton, które ilustruje dobry (i najprawdopodobniej najlepszy) sposób sortowania masywnych danych za pomocą hadoop. http://hadoop.apache.org/docs/current/api/org/apache/hadoop/examples/terasort/package-summary.html
Najpierw utworzę histogram na jednej maszynie lub na wielu maszynach. Po zliczeniu każdej możliwej wartości wiader z możliwymi wartościami można je łączyć w razie potrzeby. Wzmocnienie do korzystania z histogramu polega na tym, że ma czas wstawienia/sortowania O (1) zamiast O (log n) i wykorzystuje przestrzeń O (M), gdzie M to liczba możliwych wartości lub segmentów zamiast O (N), gdzie N jest numerem próbki.
Histogram jest sortowany w sposób naturalny, dzięki czemu można uzyskać całkowitą liczbę i znaleźć percentyle, licząc od jednego z końców.