Neue Studie vom Yahoo Lab

Fast Parallel PageRank: A Linear System Approach

Abstract:
In this paper we investigate the convergence of iterative stationary and Krylov subspace methods for the PageRank linear system, including the convergence dependency on teleportation. We demonstrate that linear system iterations converge faster than the simple power method and are less sensitive to the changes in teleportation. In order to perform this study we developed a framework for parallel PageRank computing. We describe the details of the parallel implementation and provide experimental results obtained on a 70-node Beowulf cluster.

vom Yahoo Lab
https://research.yahoo.com/

wäre schon wenn sich Super Theoretiker wie KeepCool sich das mal anschauen könnten...

@Viggen

Benötigst Du eine nicht-mathematische, verständliche Kurzfassung um die praktische Bedeutung + Auswirkungen oder eine mathematische Abhandlung über Vor- und Nachteile der Linearität / Simplifikation (Methodische Anwendung der ~) von Iterationsprozessen im Gegensatz zu derzeit verwendeten Verfahren (Googles current PR-Calculation, z.B.) ?

Gruss,

KeepCool

PS: Immer vorsichtig sein mit nicht verifizierten Attributen wie "Super", falls man die hiermit beschriebene Person und dessen Arbeiten / Publikationen nicht kennt... Nicht immer ist jemand im Internet die- / derjenige der er / sie vorgibt zu sein...Hierbei entpuppt sich oftmals die vermeintliche "Blondine des Monats" als der 1,90 m grosse, dunkelhaarige Rolf mit behaarten Waden und einem stolzen Bierbauch...:-):-)

Naja Krylov subspace und beowulf cluster klingt für mich wie aus einer Star Trek episode....

eine nicht mathematische verständliche Kurzfassung wäre schon toll

cheers
viggen

Zum Artikel:

Das Ranking / Listing einer Einzelseite (=Seite) erfolgt grundsätzlich aufgrund eines dieser Seite zugewiesenen numerischen Wertes des allg. bekannten PageRank (ist nicht nur der Google-spezifische gemeint). Mit zunehmender Anzahl an zu analysierenden Web-Dokumenten, werden bisherige Berechnungsmodelle aufgrund der Anzahl der benötigten Iterationen (Rechenvorgänge) immer mehr zum Problem; die hierfür benötigte Rechen- und Speicherkapazität würde quasi ins "Unermässliche" steigen und eine realistische und zeitnahe Kalkulation des für das Ranking benötigten PageRank-Wertes kaum noch zulassen.
Die drei im Dokument erwähnten Wissenschaftler eruiieren in dieser Abhandlung die Möglichkeit einer verschiedenartigen Berechnung des PageRanks, die zwar annähernd genau ist, jedoch weitaus weniger Rechenvorgänge benötigt und somit keine überhöhten Ansprüche an die Rechenkapazität stellt.
"Die Drei" bemühen sich um einen Lösungsansatz (quasi ein "Rechensparmodell") innerhalb komplexer (paralleler) Rechenarchitekturen: Distributed Data Modelling, Distributed Data Warehousing, Multi-Threading (Processing) [Dämonen, etc.], Parallelität der Datenspeicherung und last but not least um "Parallel Processing". Diese Vorgänge implizieren sowohl multiple Rechenprozesse wie auch (Zwischen)Speicherung von (Zwischen)Ergebnissen, ergo es geht auch um komplexe Datenhaltung - bidirektionale Replikation, die z.B. von der Standard-MySQL nicht ermöglicht wird, Master-Slave-Principle - und eine mögliche Minimalisierung der notwendigen Rechenpower.

Für die Studie wurde eine spezielle hardwaretechnische Architektur verwendet, nämlich ein Beowulf Cluster ( weitere Infos zu diesem Clustering-System: https://dune.mcs.kent.edu/~farrell/equip/beowolf/ ): diese spezielle Konfiguration mit insgesamt 140 Prozessoren und 280 GB Memory-Speicher ist - bei Anwendung der beschriebenen Rechenmethode - in der Lage, die PageRank-Berechnung für Web- und Linkstrukturen in einer Milliarden-Grössenordnung sehr schnell durchzuführen.

Um diese Rechenvorgänge (lineare Operationen) auf Cluster-Systeme durchführen zu können, haben die Wissenschaftler das allgemein bekannte "Portable, Extensible Toolkit for Scientific Computation (PETSc)" ( weitere Infos: https://www-unix.mcs.anl.gov/petsc/pets ... mentation/ ) mit individuell durchgeführten Software-Anpassungen verwendet; diese Anpassungen erlauben ihnen genaue und schnelle Zuordnungen vorhandener Vektorelemente zu anderen Bestandteilen der verwendeten Matrix...
Das Ziel ist, algorithmisch gesehen, das lineare Iterationssystem durch Vektor-Multiplikation zu ersetzen (da hierfür weniger Iterationen benötigt werden), dabei benutzt man die Krylovschen Unterraum-Methoden (weitere Infos: https://doku.b.tu-harburg.de/volltexte/2003/48/ und !!!! https://www.extenza-eps.com/extenza/loa ... e=abstract !!!! )...Stichwort: Prozess- oder Ordnungsreduktion.

So, da es ziemlich schwer fällt einem Publikum das mathematisch kaum oder unzureichend vorgebildet ist, und dadurch eh Bahnhof versteht, dieses "Zeug" weiterhin zu erklären, will ich es kurz machen:

"Die Drei" meinen eine Methode (bestehend aus Hardware-Cluster und Rechen-Methoden) gefunden zu haben, die mit verhältnismässig wenig Rechenkapazität, in der Lage ist, komplexe PageRank-Berechnungen schnell und (relativ) wertgenau durchzuführen...

Stichworte für Interessierte: Krylovscher Unterraum (Subspace) | Eigenvector | Beowulf Clustering | Chebyshevsche Iterationen

Wie (nicht nur) hier wieder einmal leicht zu ersehen, entspringen diese Grundlagen zu 95% russischen und israelischen Mathematikern und Programmieren, wie übrigens die besten Entwickler auf SUMA-Gebiet ursprünglich entweder aus Russland (ehemalige UDSSR / Ostblock) oder Israel (=jüdischen Ursprungs sind) stammen...Nix American oder German Geeks...:-):-)

Mit freundlichen Grüssen und einem grossherzigen Schalom an die bankrotte naturwissenschaftliche Bildungspolitik in Zentraleuropa und USA,

KeepCool

Danke, KeepCool!

(Du stellst dir jetzt sicher unsere Gesichter vor und kriegst dich nicht mehr ein vor Lachen...)

@Chio

Fuller hat mal gesagt - Das Wissen ist ein Schatz, aber dessen Ausübung ist der Schlüssel dazu...

Gruss,

KeepCool

@Keepcool
Meinst du Buckminster Fuller?
Heisst der Satz im Original nicht: Language is sense, knowledge, a way of ordering experience.Das meinte er aber doch wohl im Zusammenhang mit Sprache im Bezug auf seinen kapitalistischen Wert, oder?
den kann ich hier nicht erkennen:-)
Thorsten

Gerade den Thread erste gelesen und bin jetzt neugierig ob in diesem Paper auch etwas stand um wieviel das ganze wohl schneller ist.