Da will google wohl billig an schnellere Software kommen ;-)
Mich würde sowieso mal interessieren, welche Rechenleistung und welche Algorithmen bei Google bzw. bei Suchmaschinen im Einsatz sind. Wie kann man solche riesigen Datenmengen in so kurzer Zeit durchsuchen? Den Quellcode werd ich mir mal ziehen, vielleicht komm ich ja irgendwann dazu, da mal reinzuschauen...
Die Algos sind mir ja auch alle bekannt (auch wenns keine Such- sondern Sortieralgorithmen sind), aber wenn Google da noch Verbesserungspotential sieht, geht das wohl über die Standardalgorithmen hinaus. Bzw. sie werden irgendwie besonders trickreich angewandt. Sonst hätten sie das wohl auch schon selbst hinbekommen.
Achja: Ich kenne Fouriertransformation bisher nur aus der E-Technik, kannst Du mich da über den Zusammenhang zu Suchen/sortieren aufklären?
Ich denke, hier geht es sich nicht um neue Suchalgorithmen, sondern darum, wie man Bestehende am effektivsten parallelisiert, das ist nämlich ne Kunst für sich, eine Aufgabe sinnvoll auf viele Rechner zu verteilen.
Von Martin Röhricht am Mi, 6. Februar 2002 um 22:30 #
Ich sehe auch keine Anwendung von Fourier, da damit ja nur eine schnellere Polynommultiplikation erzielt werden kann (FFT). Aber wie mein Vorredner schon ansprach: Parallele Algorithmen geben da vielleicht den Ausschlag.
Hmm, Suchraum in kleinen Häppchen auf die Cluster verteilen? Sollte eigentlich recht gut parallelisierbar sein. Sag ich mal so in meiner jugendlichen Naivität ;-) Aber stimmt schon, es gibt da bestimmt noch viele Möglichkeiten zu tricksen.
@Martin Röhricht: Viel Spass mit Hashen! Die Hastables sind immer grösser als die eigentlichen Datentabellen, das mag recht lange gut gehen, aber bei Googles Datenbeständen bestimmt nicht mehr. Sicher Hashing ist schnell, aber nicht unbedingt speicher freundlich (sonst ist es nicht mehr schnell da alle Hash-Codes wenn möglich eindeutig sein sollten. Also mit Hashing alleine kommt man nicht weit bei ner Suchmaschine.
Wie überall machts die Kombination. Ein Hashtable zum Beispiel mit der IP als Key und von dortaus Trees. Natürlich bräuchte man einen zweiten Key weil Unterseiten ja über die gleiche IP-angesprochen werden (könnte man über den pfadnamen hinbekommen). Die Performance ist mathematisch gut zu belegen (findet man auch alles sehr gut beim Sedgewick beschrieben)
Ich denke hier geht es wohl eher um die Qualität der Ergebnisse. Also dass beim Suchbegriff "Samba" nicht Dieter V's "Meine besten Tanzfotos" ganz oben steht, sondern eher www.samba.org oder so.
Performanceverbesserungen durch Parallelisierung können die meisten wohl schlecht zu Hause entwickeln. (es sei denn, man kann die Rechner der ganzen WG mißbrauchen)
57MB!!! Ist das etwa alles Quellcode? Ich hätte nicht gedacht das da so viel drin ist, aber gut man lernt ja niemals aus. Bitte nicht falsch verstehen, das das mehr als 2000 Zeilen sind, war mir auch vorher klar. Mfg jensemann
Von Martin Röhricht am Mi, 6. Februar 2002 um 22:32 #
Also ich kenne Python nicht selbst, aber an C geht hier doch eigentlich kein Weg vorbei, oder? Und ich glaube auch nicht, dass hier ein Hauptbetätigungsfeld der Objektorientiertheit liegt ...
olala, also zu einer Suchmaschine gehört bekanntlich mehr, als nur der Suchalgorithmus, den der Nutzer sieht (und schätzt). Zunächst muß man crowlen, also im Web nach Webseiten suchen und die analysieren. Und das entsprechend aufbereiten, damit man dann darauf suchen kann. Dazu wird bei Google z.T. auch python verwendet. Das alles ist ziemlich komplex, um es stabil und ausreichend schnell zu machen. Das ist im wesentlichen keine Frage der Programmiersprache, sondern der Technik. Es geht hier ja nicht um den Inhalt von ein paar Festplatten ... aber dazu gibt es ziemlich viele Infos von google selbst, also wer sich dafür interessiert, der schaue doch mal bei google nach ...
Die von Goggle gelieferte Sourcen sind übrigens in C++ geschrieben. Eine gute objektorientierte Programmierung hat nur wenig mit dem Verwendungszwecks des zu erstellenden Programms zu tun.
Von Martin Röhricht am Do, 7. Februar 2002 um 14:52 #
Also Objektorientierung hat ja sehr wohl etwas mit der Verwendung zu tun. Und im allgemeinen erlebst Du Geschwindigkeitseinbussen durch OO. Du erreichst natürlich eine viel bessere Modularität und Übersicht, aber es hat schon seinen Grund, warum bspw. Treiber unter Windows in C und nicht C++ geschrieben werden.
www.alltheweb.com sind schnell und gute advanced funktionen, aber die ergebnisse sind doch leider n bischen schlechter als google :)is nur noch suchmaschine 2. wahl
Google ist zwar anscheinend echt gut und so weiter, aber es würde mich schon mal interessieren, warum deren Spider nicht über dynamische Webseiten geht. Vielleicht sollte "man" das mal implementieren, sonst geht in naher Zukunft ein grosser Teil der Informationen an Google vorbei...
Überleg mal, wieso. Was macht es für einen Sinn, heute eine Seite zu indizieren, die morgen oder eine Stunde später schon einen anderen Inhalt haben kann? Da kommt es eher auf gute Archivierung an.
Es ist mittlerweile (google) egal, ob eine Datei mit *.html, *.php oder was weiß ich endet. Auch werden Parameter beachtet (index.php?page=2 etc.) und bei der Indizierung berücksichtigt.
@ Andreas: Ds kann mit HTML-Seiten auch passieren, oder? Der einzige Unterschied ist, dneke ich, dass HTML-Seiten per FTP und dynamische Seiten per HTTP, ODBC oder sonst wie aktualisiert werden.
@ Heiko: Echt? Gute Neuigkeiten. Muss ich gleich mal ansehen...
Also, ich bezweifle, dass jemand einen noch schnelleren Algo hinkriegt, als die von Google. Hinter Google stecken viele Software-Ingenieure, die lange gearbeitet haben, und die sind auch nicht blöd. Jetzt soll einer einfach kommen und in dieser kurzen Zeit so aus dem Ärmel einen besseren Algo, der alle anderen Suchmaschinen in fast allen Punkten schlägt, schütteln?
Also wenn ich den englischen Text richtig gelsen habe soll der eingesendete Code etwas ineterressantes mit den Daten machen. Also denke ich mal, dass die eher auf der Suche nach neuen Funktionen sind...
Glaubt ihr wirklich, dass in dem downloadbaren Archiv die "original" Google Suchmaschine steckt, denn wenn das wirklich so wäre, hätte sie ja ihren technologischen Vorsprung gegenüber anderen Suchmaschinen in programmtechnischer Hinsicht verloren ?!
He, He! Dann brauchst du ja mindestens so grosses Entwicklerteam, wie es google hat um die Sourcen anzupassen und zu sichten. Wenn alle Informationen immer und ewig geheimgehalten wordne wären, hätte sich die Menschheit nie entwickelt. It's for the future, not for now!
Mich würde sowieso mal interessieren,
welche Rechenleistung und welche Algorithmen bei Google bzw. bei Suchmaschinen im Einsatz sind.
Wie kann man solche riesigen Datenmengen in so kurzer Zeit durchsuchen?
Den Quellcode werd ich mir mal ziehen, vielleicht komm ich ja irgendwann dazu, da mal reinzuschauen...
Wenn du dich dafür interessierst, solltest du entweder Informatik studieren oder ein gutes Algorithmenbuch über Suchalgorithmen kaufen ;)
Was recht interessant ist z.B. Fourier-Transformation, Binärbäume verknüpft mit den bekannten Suchalgorithmen wie Heapsort, Quick-, Mergesort.
Da hast Du ja dann bei so riesen Datenmengen gewonnen.
Die Algos sind mir ja auch alle bekannt (auch wenns keine Such- sondern Sortieralgorithmen sind),
aber wenn Google da noch
Verbesserungspotential sieht, geht
das wohl über die Standardalgorithmen
hinaus. Bzw. sie werden irgendwie besonders trickreich angewandt.
Sonst hätten sie das wohl auch schon selbst hinbekommen.
Achja: Ich kenne
Fouriertransformation bisher nur
aus der E-Technik, kannst Du mich da
über den Zusammenhang zu Suchen/sortieren aufklären?
Aber wie mein Vorredner schon ansprach: Parallele Algorithmen geben da vielleicht den Ausschlag.
Suchraum in kleinen Häppchen auf die Cluster verteilen? Sollte eigentlich
recht gut parallelisierbar sein. Sag ich mal so in meiner jugendlichen
Naivität ;-)
Aber stimmt schon, es gibt da bestimmt noch viele Möglichkeiten
zu tricksen.
Sicher Hashing ist schnell, aber nicht unbedingt speicher freundlich (sonst ist es nicht mehr schnell da alle Hash-Codes wenn möglich eindeutig sein sollten.
Also mit Hashing alleine kommt man nicht weit bei ner Suchmaschine.
Ich denke hier geht es wohl eher um die Qualität der Ergebnisse. Also dass beim Suchbegriff "Samba" nicht Dieter V's "Meine besten Tanzfotos" ganz oben steht, sondern eher www.samba.org oder so.
Performanceverbesserungen durch Parallelisierung können die meisten wohl schlecht zu Hause entwickeln. (es sei denn, man kann die Rechner der ganzen WG mißbrauchen)
Schöne Grüsse, Prefect
Ist das etwa alles Quellcode? Ich hätte nicht gedacht das da so viel drin ist, aber gut man lernt ja niemals aus. Bitte nicht falsch verstehen, das das mehr als 2000 Zeilen sind, war mir auch vorher klar.
Mfg jensemann
CU Dom
oder saugen:
>http://research.google.com/contest/prog-contest-sample.tar - 57M
Irgendwas passt da nicht, oder?
Mfg jensemann
das es ein cluster sein soll aus mehreren rechnern (!) hat mich auch überrascht!!
hehe, google ist halt DIE linux suchmaschine!!
steht bei mir im wohnzimmer
Yahoo z.B.
Aber Moment, der kauft ja von Google ein
oder ist es in jython implementiert?
oder war das mit python eine fehlinfo?
Und ich glaube auch nicht, dass hier ein Hauptbetätigungsfeld der Objektorientiertheit liegt ...
dil
Und im allgemeinen erlebst Du Geschwindigkeitseinbussen durch OO. Du erreichst natürlich eine viel bessere Modularität und Übersicht, aber es hat schon seinen Grund, warum bspw. Treiber unter Windows in C und nicht C++ geschrieben werden.
www.alltheweb.com sind schnell und gute advanced funktionen, aber die ergebnisse sind doch leider n bischen schlechter als google :)is nur noch suchmaschine 2. wahl
Vielleicht sollte "man" das mal implementieren, sonst geht in naher Zukunft ein grosser Teil der Informationen an Google vorbei...
Greets
Es ist mittlerweile (google) egal, ob eine Datei mit *.html, *.php oder was weiß ich endet. Auch werden Parameter beachtet (index.php?page=2 etc.) und bei der Indizierung berücksichtigt.
Ds kann mit HTML-Seiten auch passieren, oder?
Der einzige Unterschied ist, dneke ich, dass HTML-Seiten per FTP und dynamische Seiten per HTTP, ODBC oder sonst wie aktualisiert werden.
@ Heiko:
Echt?
Gute Neuigkeiten. Muss ich gleich mal ansehen...