Zeitkomplexitätsanalyse für das Map-Reduce-Modell

Ich versuche, meinen Algorithmus so zu gestalten, dass er auf dem Hadoop / MapReduce-Paradigma ausgeführt wird. Ich habe mich gefragt, ob es einen ganzheitlichen Ansatz zur Messung der Zeitkomplexität für Algorithmen auf Big Data-Plattformen gibt.

Als einfaches Beispiel kann für O (n) + C ein Durchschnitt von n (= 1 Milliarde) Zahlen genommen werden (unter der Annahme, dass die Division eine konstante Zeitoperation ist). Wenn ich diesen massiv parallelisierbaren Algorithmus für Map Reduce durch Teilen von Daten über k Knoten unterbreche, wird meine Zeitkomplexität einfach zu O (n / k) + C + C '. Hier kann C 'als Zeitaufwand für die Planung des Startjobs angenommen werden. Beachten Sie, dass kein Mischen erforderlich war und die Arbeit des Reduzierers fast trivial war.

Ich interessiere mich für eine vollständigere Analyse des Algorithmus mit iterativen Schleifen über Daten und mit umfangreichen Misch- und Reduzierungsoperationen. Ich möchte, wenn möglich, die E / A-Operationen und Netzwerkübertragungen von Daten einbeziehen.

S. Arora, B. Barak, Moderner Ansatz der Computerkomplexität, Kapitel 13 ist eine gute Einführung in dieses Thema:

Die Kommunikationskomplexität betrifft das folgende Szenario. Es gibt zwei Spieler mit unbegrenzter Rechenleistung, von denen jeder eine besitzt$n$ Biteingabe, sagen wir $x$ und $y$. Keiner kennt die Eingabe des anderen und möchte diese gemeinsam berechnen$f(x, y)$ wo die Funktion $f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\}$ist beiden bekannt. Darüber hinaus hatten sie diese Situation vorausgesehen (z. B. könnte eine der Parteien ein Raumschiff und die andere die Basisstation auf der Erde sein), also hatten sie dies bereits getan - bevor sie ihre Eingaben kannten$x, y$- ein Protokoll für die Kommunikation vereinbart. Die Kosten dieses Protokolls sind die Anzahl der Bits, die von den Spielern für die Auswahl der Eingänge im ungünstigsten Fall übertragen werden$x, y$.

Sie sehen, Sie haben Recht, aber Sie wissen, dass es ziemlich schwierig ist, eine bestimmte zeitliche Komplexität der Kartenreduzierung zu sagen. Das hängt von der Abfrage ab. In diesem Fall sollte es jedoch wegen k Knoten o (nlogn / k) + c + c 'sein. Diese kurzen Abfragen, einschließlich einer Mapping-Phase einer kartenreduzierenden Texhnique, folgen einem Btree-Konzept. Von diesem Ort aus können wir für innere Berechnungen sagen, dass seine zeitliche Komplexität> o (nlogn) + c + c 'ist.

Korrigieren Sie bitte meine Vorschläge.