Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Ideen und Vorschläge sind willkommen.

Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon PCA42 » Sa Mär 28, 2009 10:32 pm

Mir ist heute eine Idee gekommen, wie man die Daten anders bei einer P2P-Suchmaschine organisieren kann. Ich fang einfach mal an.

Grundidee hinter der Geschichte ist, dass die Webseiten nicht wie bisher in ihre Worte zerlegt und dann verteilt werden. Vielmehr werden die Seite im Stück auf einem Peer gehalten. Damit nun die Verteilung und umgekehrt die Suche funktioniert, müssen die Seiten anders auf die Peers verteilt werden.

Dabei versucht jeder Peer, die bei ihm über alle Seiten vorhandenen, unterschiedlichen RWIs zu reduzieren. Er spezialisert sich somit auf einen bestimmten Wortbereich und wird für diesen Wortbereich mit der Zeit ein Spezialist. Er versucht also gezielt Seiten auf andere Peers zu verteilen, die am meisten von den vorhandenen RWIs abweichen.

Damit dies funktioniert, müssen alle Peers im Netz die RWIs der anderen kennen. Beim Ping der Peers untereinander werden Teile der RWI-Liste mit der Anzahl der jeweiligen Worte übermittelt. Peer A teilt also Peer B mit, dass er das Wort "xyz" 20000 mal in seinem Index hat, das Wort "yyy" 10000 mal usw. Da dieser Datenaustausch umfangreicher sein kann, werden immer nur Teile übermittelt. Peer A merkt sich jedoch die übermittelten Teile und schickt beim nächsten Ping nur noch Ergänzungen und Änderungen.

Wenn diese Kenntnis der Peers untereinander vorhanden ist, kann ich also Seiten, die wenig zu meinem Peer passen, gezielt an passendere Peers senden. In diesem Schritt kann dann auch die Redundanz einfließen. Ich schicke halt die Seite an die ersten n-passenden Peers.

Die Suche wird bei diesen Kenntnissen der Peers übereinander auch zum Kinderspiel: ich kann gezielt Peers ansprechen, die die passenden RWIs vorrätig haben. Wenn dabei die Suchphrase mit übermittelt wird, kann in der gespeicherten vollständigen Seiten eine Suche mit allen Schikanen (z.B. Phrase in Gänsefüßchen) erfolgen.

So, ich hoffe ich habe alles verständlich darbringen können und bin auf eure Kommentare gespannt.
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon PCA42 » So Mär 29, 2009 7:25 pm

Auf diesem Weg würden sogar Themenpeers auf alle vorhandenen Worte ansprechen.... Aber warum schreib ich das hier eigentlich. :(
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon Orbiter » So Mär 29, 2009 8:05 pm

Diese Idee kann man realisieren, das nennt sich 'Partition by Document' im Gegensatz zum 'Partition by Key' wie in unserer DHT.
PCA42 hat geschrieben:Peer A teilt also Peer B mit, dass er das Wort "xyz" 20000 mal in seinem Index hat, das Wort "yyy" 10000 mal usw. Da dieser Datenaustausch umfangreicher sein kann, werden immer nur Teile übermittelt. Peer A merkt sich jedoch die übermittelten Teile und schickt beim nächsten Ping nur noch Ergänzungen und Änderungen.

Das hört sich komlex an. Im Prinzip heisst das, das jeder Peer dann wissen muss was jeder andere Peer in seinem Index hat. Dadurch wird zwar vermieden, dass man alle Peers bei einer Suche fragen muss, aber man brauch doch eine recht große Datenbank, die mit der Anzahl der Peers mitskalieren muss. Das Skalierungsproblem, das bei einer DHT durch eine einfache mathematische Formel gelöst wird, wird hier durch eine stetig wachsende Datenbank gelöst. Ich finde das auch recht aufwendig.

Es gibt wohl auch Papers über die Vor- und Nachteile von Partition by Document/Key; hier habe ich was gefunden:
http://www.nvc.cs.vt.edu/~cegyhazy/cs56 ... ibuted.ppt
Ich finde ja, dass der Verwaltungsaufwand um zu wissen welchen Peer man fragen soll unüberschaubar wird, wenn es um wirklich viele Peers geht. Darum finde ich Partition by Key einfacher, auch wenn das Verteilen aufwendig ist. Das ist halt bei der Suche einfacher.

Das Max-Planck Institut für Informatik hat ein P2P-Projekt, das Websuche mit Partition-by-Document macht:
http://www.mpi-inf.mpg.de/departments/d ... index.html
Ich habe da vor drei Jahren mal einen email-Austausch mit den Leuten gehabt, um herauszufinden wie die das machen. Das was ich da verstanden habe war, das man von jedem Dokument so eine Art 'Abstract' erzeugt, das an alle Peers verteilt wird, und das für das Routing der Suche genutzt wird. Ich fand dass das eine ziemlich unvollständige Herangehensweise war, und wie dieser 'Abstract' erzeugt werden sollte konnten die mir auch nicht genau sagen. Ich hatte den Eindruck die wissen es nicht genau. Daher hatte mir diese Methodik nicht gut gefallen, weil zu viele Fragen nicht geklärt werden konnten.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon PCA42 » Mo Mär 30, 2009 5:06 am

Dabei versucht jeder Peer, die bei ihm über alle Seiten vorhandenen, unterschiedlichen RWIs zu reduzieren. Er spezialisert sich somit auf einen bestimmten Wortbereich und wird für diesen Wortbereich mit der Zeit ein Spezialist. Er versucht also gezielt Seiten auf andere Peers zu verteilen, die am meisten von den vorhandenen RWIs abweichen.

Das Gruppieren der Dokumente auf Peers nach ihren Eigenschaften ist in beiden von dir angeführten Links nicht mit eingebaut. Das Ganze sollte dadurch skalieren, daß mit steigender Menge an Peers die jeweilige Menge an RWIs, für die ein Peer zuständig ist, sinkt. Dies soll ja grade durch das Verteilen der Dokumente erreicht werden. Minvera verteilt z.B. die Dokumente nicht. Aber auch wenn jemand seine Daten nicht verteilt funktioniert die Suche in diesen Daten. Er trägt dann aber selber den erhöhten Aufwand auf seinem Peer.
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon wobble » Mi Apr 01, 2009 12:41 pm

hmm .. ich kann mir vostellen, dass eine solche Struktur durchaus Vorteile bringen könnte. Allerdings denke ich, dass es vorher sinnvoll ist Vorteile/Nachteile herauszuarbeiten. Am besten, indem wir die Ergebnisse im Wiki festhalten. Ich hab vor kurzem nen recht allgemein gehaltenen Artikel über den Index aufgemacht: http://www.yacy-websuche.de/wiki/index.php/Dev:Index
Ich denke, dort sollten solche Vorschläge rein, bzw. verlinkt sein. Am besten du machst nen neuen Artikel auf, wo Vor- und Nachteile diskutiert werden können.

Einen Aspekt, den ich wichtig finde, ist dass auch Suchanfragen effektiv beantwortet werden können sollten, die nicht nur aus einem Wort bestehen.

Nun noch was inhaltlich zu deinem Vorschlag:
Ein Vorteil, den ich sehe, ist dass die Wörter, die ein Peer speichert, alle miteinander zutun haben. Das heißt insbesondere, dass man eventuell nicht für alle gespeicherten Wörter unabhängige Page-Ranknings machen muss. Dementsprechend reduziert sich auch die Mange von Pagerankings für Wort-tupel enorm.
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon PCA42 » Mi Apr 01, 2009 7:04 pm

Jepp, ist wahrscheinlich besser, im Wiki die Idee etwas zu verfeinern. Ich mach mich mal ans Werk....

Edit: Hab die Diskussionsseite dafür genommen -> >Kalick<
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon wobble » Mi Apr 01, 2009 10:16 pm

hab nen bisl was ergänzt, teilweise Ideen, die ich mit meinem Trie-DHT-Vorschlag in ähnlicher Art und Weise geäußert habe, bzw. auf die ich gekommen bin als ich versucht hab den Vorschlag zu implementieren und die eventuell wiederverwertbar sind.

Da du angefangen hattest auf der Wiki-Seite in deutsch zu schreiben, hab ich jetzt auch in deutsch weitergeschrieben, auch wenn es denke ich durchaus sinnvoll wäre solche Sachen in Englisch festzuhalten, um auch anderssprachigen Entwicklern die Möglichkeit zu geben mitzuhelfen. (ich weiß, in der Muttersprache kann man sich doch viel leichter ausdrücken ;)
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon PCA42 » Do Apr 02, 2009 5:01 am

wobble hat geschrieben:Da du angefangen hattest auf der Wiki-Seite in deutsch zu schreiben, hab ich jetzt auch in deutsch weitergeschrieben, auch wenn es denke ich durchaus sinnvoll wäre solche Sachen in Englisch festzuhalten, um auch anderssprachigen Entwicklern die Möglichkeit zu geben mitzuhelfen. (ich weiß, in der Muttersprache kann man sich doch viel leichter ausdrücken ;)

Stehen leider mit dem Verfassen von englischen Texten auf Kriegsfuß. Lesen alles schön. Aber schreiben :oops:
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon Orbiter » Do Apr 02, 2009 4:19 pm

ihr könnt vielleicht verstehen das eine völlige Änderung der Verteilungsstrategie jetzt ein wenig ungünstig ist, man müsste ja mit einem neuen Netz anfangen. Das könnte man sicherlich auch tun, aber an der aktuellen DHT-Verteilung knobele ich nun schon sehr lange, thq wird sich erinnern das ich einen Scan aus meinen kleinen schwarzen Buch für die neue DHT schon vor über einem Jahr gepostet habe.

Je nach Art der Daten, der User und der Art das Netz aufzubauen kann es aber sicherlich richtig sein, die Daten anders zu verteilen. Beim Sciencenet ist es beispielsweise so, dass gar nicht verteil wird, weil dort die Abfrage aller Peers möglich ist und auch schnell ist, und es sich viele Vorteile daraus ergeben. Beim freeworld-Index ist die DHT ein Proof-of-Concept für eine DHT, bei der es auch millionen Teilnehmer geben könnte. Ich möchte das jetzt nicht ändern.

Trotzdem könnt ihr euch Gedanken zu dem Thema machen, und es ist auch jetzt sehr viel einfacher ein ganz neues Schema für die Verteilung einzubauen. Bitte dazu mal das Interface de.anomic.yacy.dht.PartitionScheme.java angucken, das ist jetzt so weit abstrahiert das man da nur das Interface implementiert, und damit ein eigenes Schema einbinden kann. Bitte denkt darüber nach, das dann auch selber zu machen. Ich habe an dieser Stelle das Thema vertikale DHT zwar fertig, aber wahrscheinlich noch nicht alles gefixt und werde da erst mal bei bleiben, denn es gibt ja noch so viele andere Baustellen, die ich momentan erheblich wichtiger finde.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon PCA42 » Do Apr 02, 2009 4:31 pm

Orbiter, ich möchte keineswegs aufdringlich sein. Mir schießen manchmal Ideen in den Kopf, wie man Sachen vielleicht anders machen kann. Wenn das nicht in dein Konzept passt oder Denkfehler vorhanden sind, schreib das einfach kurz. Es ist mir bewußt, dass ich hier in meiner Rolle als Tester hinsichtlich des Konzeptes keinen Einfluß nehmen kann.

Deshalb werd ich mich auch in Zukunft nicht entmutigen lassen und weiterhin Ideen hier einbringen. Wenn die nicht ins Konzept passen, schreib das einfach kurz. Damit kann ich umgehen. 8-)
Außerdem: ich spiel gern mit Software rum. Yacy zu testen ist da sehr abwechslungsreich.
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon Huppi » Do Apr 02, 2009 7:26 pm

Wenn solche Ideen von den Vorschlagenden auch realisiert werden, dann kann man das in einem neuen Netzt ja durchaus mal ausprobieren.
Solange die Hauptentwickler Zeit haben, sich um die dringenden und wichtigen Sachen zu kümmern, habe erprobte Parallelkonzepte ja einen riesigen Wert im Rahmen der Weiterentwicklung des Projektes.
Huppi
 
Beiträge: 898
Registriert: Fr Jun 29, 2007 9:49 am
Wohnort: Kürten

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon wobble » Fr Apr 03, 2009 10:54 am

Also ich sehe den Mehrwehr einer solchen Diskussion hauptsächlich darin, dass man versteht, was die Probleme genau sind.
Wenn jemand einen neuen Vorschlag macht, wie das mit Verteilung vlt. besser gelöst werden könnte, so stellt sich nach meiner Erfahrung häufig raus, dass unnötige Probleme besser gelöst werden und nicht wirklich die Kernprobleme. Allerdings ist es riesige unnötige Arbeit, wenn die erst herausgefunden wird, wenn der Kram schon implementiert ist.

Deshalb habe ich ja auch angefangen den Wiki Artikel zu schreiben um herauszufinden, was denn wirklich die harten Probleme sind, die noch geknackt werden müssen (keiner kann mir erzählen, dass die aktuelle Lösung schon optimal ist - dafür ist das Problem viel zu kompliziert). Meiner Meinung nach, z.b. ist das die Suche mit mehreren Suchwörtern und das damit verbundene Ranking der Ergebnisse. Allerdings kann es auch sein, dass ich darin total falsch liege.

Somit möchte ich noch was zu meinem und PCA42's Vorschlägen sagen:
  • Ich denke mein Vorschlag löst ein paar Probleme, die die aktuelle Implementierung vom DHT hat. Allerdings kommen zusätzliche Probleme hinzu und am wichtigsten: Mein Vorschlag löst meiner Meinung nach nicht das Kernproblem (Suche mit mehr als einem Suchwort)!
  • PCA42's Vorschlag tendiert unter Umständen dazu die Möglichkeit zu bieten das "meiner Meinung nach Kernproblem" lösen zu können. Allerdings ist der Vorschlag bei weitem nicht so ausgereift, als dass man diesen implementieren könnte.

Falls jemand wirklich eine gute Idee hat, wie der Index verbessert werden kann, werde ich demjenigen helfen das auszuprobieren. Dafür muss aber objektiv analysiert werden können, dass die Idee wirklich substantiell besser ist. Das ist meiner Meinung nach der Sinn dieser Diskussion und es ist nicht das Ziel die aktuelle Lösung schlecht zu machen.

Somit denke ich es wäre voll cool, wenn bekannt und dokumentiert wäre, was die größten Nachteile/Vorteile der aktuellen Implementierung sind. Das weiß normalerweise derjenige, der das Ding geschrieben hat am besten (also ich vermute mal du, Orbiter ;-) ). Dann gibts vlt. auch nicht soviel unnötige und blödsinnige Vorschläge ;)

cheers
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: Verteilung der Daten mit mehr Möglichkeiten bei der Suche

Beitragvon Orbiter » Fr Apr 03, 2009 11:40 am

PCA42, ich möchte nicht das der Eindruck entsteht, ich wolle deine Idee mies machen um nicht vom einmal eingeschlagenen Pfad abrücken zu wollen oder den Aufwand zu scheuen. Es ist im Gegenteil so, dass deine Idee schon knackig ist, und die erste Betrachtung zeigt schon einen gewaltigen Aufwand, denn man müsste die bis jetzt abstrahierten Verteilungsregeln wohl stark erweitern, neue Datenbanken bauen für die Speicherung der Verteilprofile der anderen Peers, und neue Protokolle für den Austausch der Informationen dazu. Wie wobble anspricht wird dadurch ein Kernproblem, die Mehrwortsuche ein wenig besser gelöst als aktuell. Aber das ist vielleicht nur auf den ersten Blick so, denn es ist 'nur' eine 'gefühlte' Verbesserung. Die aktuelle DHT liefert ja eine Antwort auf das Problem der Mehrwortsuche, sie ist nur sehr komplex (es geht um die IndexAbstracts die bei einer verteilten Suche mitgeliefert werden und dazu führen in einer 2. Suche die Index-Konjunktion verteilt aufzulösen). Deine Lösung hat die Komplexität woanders, nämlich bei der Aufgabe überhaupt Zielpeers bei der Suche zu berechnen .. und darum geht es ja bei der Verteilung. Die aktuelle DHT liefert darauf eine ganz einefache Antwort, nämliche eine einfache Berechung, eben eine Hash-Berechnung. Bei PCA42s Idee wird das Ziel aufgrund des Auslesens einer immer weiter angereicherten (und revidierten?) lokalen Datenbank erreicht.

Möglicherweise kann man die Idee vorsichtig in Anfragestrategien/Heuristiken einbauen. Wir haben ja bereits was ähnliches, und zwar die Peer Tags. Mit den Peer Tags macht ein Peer eine Spezialisierung seines Indexes bekannt, und er kann bei der Suche zusätzlich zu den DHT-Targets hinzugezogen werden. Das ist schon ein ganz kleines bisschen so wie mit deiner Info-Datenbank. Anstelle alles umwerfen zu wollen müssten wir herausfinden was einfach zu machen wäre und ggf. viel bringt.
Orbiter
 
Beiträge: 5796
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main


Zurück zu Wunschliste

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot] und 2 Gäste