DHT Vorschläge für Indizierung

Ideen und Vorschläge sind willkommen.

DHT Vorschläge für Indizierung

Beitragvon wobble » Fr Mär 13, 2009 1:30 pm

Hi
ich weiß, dass ihr gerade auf eine neue DHT umstellt (jedenfalls scheint mir das aus den Posts so), und somit mag es sehr arrogant klingen, wenn ich jetzt hier nen neuen Vorschlag mache, wie man (meiner Meinung nach) einen sinnvollen Index aufbaut. Ich will somit erstmal betonen, dass ich nicht arrogant klingen möchte und mein Vorschlag nur als Idee bzw. Anregung gedacht ist. Nicht, dass es nachher heißt, hätteste du aber auch früher schonmal ertählen können oder so.
Ich konnte letzte Nacht nicht gut einschlafen, somit hat sich quasi aus einer Idee ein riesiger Haufen an Ideen gebildet, die allerdings aufeinander aufbauen.

Grundidee:
Speicherung der Wörter in einem Trie. D.h. wenn man das freeworld Netz betrachtet, so zerteilt sich dieses in mehrere Subnetze, jedes dieser Subnetze ist für einen Buchstaben zuständig. Mit Subnetz meine ich jetzt nicht Subnetze im Klassischen Sinn, sondern einfach Gruppierungen von Peers. Dabei kann ein Peer auch Mitglied in mehreren Subnetzen sein.
Jedes Subnetz wiederum unterteilt sich wieder in Subnetze für den zweiten Buchstaben usw. Ist ein Peer in einem solchen Solchen Subnetz (z.B. für "ab", so ist er auch autmatisch in dem Subnetz für "a"). Dieser Peer ist dann quasi "Experte" für alle Wörter, die mit "ab" beginnen. Dafür muss er nicht alle Wörter, die mit ab beginnen speichern, sondern kann wenn Anfragen kommen diese an die mehr spezialisierten Peers weiterleiten.
Wird also nach dem Wort "abacus" gesucht, so stellt der Suchende eine Anfrage an einen beliebigen Peer, der für "a" zuständig ist. Dieser Peer leitet die Anfrage weiter an einen Peer, der für "ab" zuständig ist, welcher das an den Peer für "aba" weiterleitet und dieser hat vielleich den Rest in seinem lokalen Index und kann dann das Suchergebnis für abacus zurückgeben.
Jeder Peer kennt also mindestens einen Peer aus jedem Nachbarsubnetz.

Erweiterung 1
Sollten das zu viele Nachbarn sein, so könnte man die einzelnen Buchstaben noch Gruppieren. Dann sind also die obersten Subnetz nicht nach Buchstaben, sondern nach Buchstabengruppen sortiert.
Da mit jeder Ebene mehr Kommunikationsaufwand verbunden ist, kann man das Verhalten der Peers auch so spezifizieren, dass sie die Anfrage an denjenigen Peer weiterleiten, der nach ihrer Meinung am geeignesten ist. Also wenn der Peer, der Experte für "a" ist auch schon nen Peer kennt, der Experte für "aba" ist, so muss kein Umweg über einen anderen "ab" Peer gemacht werden.

Erweiterung 2
Der Vorteil eines Tries ist, dass wenn ich nach "friends" suche, der automatisch bei der Suche auch das Wort "friend" besucht, da es ein Präfix von "friends" ist. Ebenso können leicht Treffer für Wörter gefunden werden, die "friend" enthalten. Somit können sehr leicht viele neue semantisch gut passende Treffer erzeugt werden. Speichert man zusätzlich auch alle Suffixe der Wörter, so werden auch Wörter wie "penfriend" gefunden.

Erweiterung 3
Dies kann man noch weiter auf die Spitze treiben, wenn man anstelle der Wörter eines Dokumentes einfach alle Suffixe des Dokumentes indiziert. Siehe dazu http://de.wikipedia.org/wiki/Suffixbaum.
Benutzt man dazu komprimierte Tries, so benötigt man nicht wesentlich mehr Speicher, als das Dokument lang ist (also O(n) Speicher, bei einem n Zeichen langen Dokument).
Dann kann man auch nach Wortpaaren geziehlt suchen, also z.B. nach "girl friend" und findet nur Treffer, wo diese beiden Wörter auch direkt hintereinander vorkommen. Implizit, kann man dann sogar noch mitspeichern, wo im Text genau dieses Wort sich befindet und somit kann man eine Vorschau des Textes an der relevanten Stelle machen (ein Feature, dass ich bei der Bewertung von Suchergebnissen fast ausschließlich verwende).

Erweiterung 4
Eventuell ist es sehr zeitaufwändig, wenn nach "friend" gesucht wird, den gesamten Teilbaum unter "friend" zu durchsuchen, um alle Treffer zu finden (evtl. weil mit anderen Peers kommuniziert werden muss). Um das zu verbessern könnte man an jedem Knoten im Trie eine "Top 10" verwalten, die die meist zurückgegebenen Ergebnisse (bei Anfragen an den Unterbaum) enthält. Diese Ergebisse kann man an den Anfragen schon am Anfang der Suche schicken, und dann nachher noch mehr bessere Ergebnisse nachliefern.

Wie man die Suche bei mehreren Wörtern gestaltet (also wenn die Wörter nicht hintereinander vorkommen müssen) am besten verfährt, hab ich mir jetzt noch keine wesentlichen Gedanken gemacht. Möglich wär dass man für jedes Wort getrennt sucht und über die Ergebnisse einen Filter laufen lässt oder so. Aber ich denke das Problem hat man mit fast allen Indizierungsmethoden, vlt. habt ihr da ja schon was gutes entwickelt.

Nachteile
  • Benötigt zum Speichern der gleichen Anzahl von URLs wesentlich mehr Speicherplatz (bei Erweiterung 3 werden alle Seiten archiviert)
  • Inkompatibel zum aktuellen System (man müsste einen zweiten Index parallel aufbauen, ähnlich also wie als bei eMule irgendwann Kad dazukam)
  • Tippfehler können nicht erkannt werden (Da die gesuchten Wörter dann keine Teilwörter mehr sind), aber eventuell kann man das auch noch irgendwie geschickt beheben.

Vorteile
  • Detailierte Ergebnisse
  • Würde man alle Wortpaare und Teilwörter zusätzlich indizieren, würde man klassisch (mit Wort-Hashes) noch mehr Speicherplatz benötigen
  • Schnelle Ergebnisse (auch wenn am Anfang vlt. nicht gute Treffer)
  • kein Rehashing, für Redundanz können einfach ganze Teilbäume kopiert werden.
  • Kein Caching von Wörtern, sondern von Präfixen, diese sind auch für ähnliche Wörter zu gebrauchen.

uff.. ist jetzt ganz schon lang geworden, ich hoffe ihr hattet die Ausdauer das durchzulesen ;)
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: DHT Vorschläge für Indizierung

Beitragvon Orbiter » Fr Mär 13, 2009 2:07 pm

schönes Modell, aber wir haben noch mehr Kriterien, die sowas hier schwierig macht. Beispiel:

Redundanzen notwenig: was wenn ein Peer aus ist? dann geht ein ganzer Teilbaum über die Wupper. Wir haben einfach Alternativpositionen.

die Verteilung der Buchstaben und aufgliederung in Teilbäume kann man durchaus als Instanz unserer (alten) Wortbasierten DHT sehen. Insofern nichts neues, nur das die Formalisierung mit Tries das ganze diskret definiert, aber leider nicht in einem unstabilen Netz funktioniert. Was hier fehlt ist die vertikale Skalierung, d.h. eine performance-Orientierte Skalierung. Du musst dir vorstellen, das du dein Trie in x Teil-Tries aufteilst, die du dann bei einer Suche simultan ansprichst, um aus der geringeren Datenmenge der einzelen Peers per parallelisierung mehr Geschwindigkeit raus zu holen. Du brauchst also mehrere Tries, kannst die aber auf alle Peers wieder abbilden? Wir haben hier jetzt eine Lösng durch eine sehr einfache Partitionierung des Indexes mit Hilfe der URL-hashes, was effektiv dafür sorgt das quasi eine URL-DHT mit einer Wort-DHT 'übereinandergelegt' in eine Matrix abgelegt, und auf die Seeds in Ringform gemappt wird.
Orbiter
 
Beiträge: 5793
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: DHT Vorschläge für Indizierung

Beitragvon wobble » Fr Mär 13, 2009 3:18 pm

Orbiter hat geschrieben:schönes Modell, aber wir haben noch mehr Kriterien, die sowas hier schwierig macht. Beispiel:

Redundanzen notwenig: was wenn ein Peer aus ist? dann geht ein ganzer Teilbaum über die Wupper. Wir haben einfach Alternativpositionen.

Redundanzen kriegste rein, in dem nicht nur einzelne Peers für Teilbäume zu ständig sind. Also es können ja mehrere Peers z.b. Wörter, die mit "aba" beginnen indiziert haben. Also "abacus" kann ja bei mehreren Peers gespeichert sein.
die Verteilung der Buchstaben und aufgliederung in Teilbäume kann man durchaus als Instanz unserer (alten) Wortbasierten DHT sehen. Insofern nichts neues, nur das die Formalisierung mit Tries das ganze diskret definiert, aber leider nicht in einem unstabilen Netz funktioniert. Was hier fehlt ist die vertikale Skalierung, d.h. eine performance-Orientierte Skalierung. Du musst dir vorstellen, das du dein Trie in x Teil-Tries aufteilst, die du dann bei einer Suche simultan ansprichst, um aus der geringeren Datenmenge der einzelen Peers per parallelisierung mehr Geschwindigkeit raus zu holen. Du brauchst also mehrere Tries, kannst die aber auf alle Peers wieder abbilden?

man kann ja z.B. bei einer Suche nach "abacus" mehrere zuständige Peers kennen und die auch parallel befragen. Also z.B. kennt man Peers, die für "a", "abac", "ab" zuständig sind, dann kann man die Anfrage an diese parallel weiterleiten. Der "abac"-Peer ist so spezialisiert, der wird das Wort vermutlich im lokalen Index finden. Der "a"-Peer wird vermutlich nicht seinen lokalen Index befragen, da er zu unspezialisert ist, und befragt spezialisiertere Peers. Eventuell befragt dieser wiederum unter anderen den "abac"-Peer, die doppelte Anfrage kann aber anhand einer zufälligen Anfrage-ID geprüft werden. Der "ab" Peer macht vlt. beides.
Wir haben hier jetzt eine Lösng durch eine sehr einfache Partitionierung des Indexes mit Hilfe der URL-hashes, was effektiv dafür sorgt das quasi eine URL-DHT mit einer Wort-DHT 'übereinandergelegt' in eine Matrix abgelegt, und auf die Seeds in Ringform gemappt wird.

mmh... da stellt sich mir die Frage des Routings. Ok, aktuell sind c.a. 80 Peers aktiv, da ist es kein Problem Verbindungen zu allen Peers offenzuhalten. Sobald das mehr Peers werden, kann man keine Verbindungen zu allen Peers aufrechterhalten und dann kann man die Peers auch wieder nur in O(log n) ansprechen.

Bei wenigen Peers kann bei meinem Verfahren auch jeder Peer wissen, welcher Peer was indiziert hat und diesen dann direkt ansprechen. Das war mein Vorschlag von Erweiterung 1.
Bei vielen Peers wird mein Vorschlag (abhängig von der Implementierung) auch Verbindungen in O(log n) herstellen (desto mehr Peers es gibt, desto anteilig weniger spezialisierte Peers sind dann je Peer bekannt). Vom Aufwand dürfte sich das im Grunde nicht wesentlich unterscheiden.
Wesentlicher Unterschied ist meines Erachtens, dass bei meinem Vorschlag das Routing mit der Semantik der Anfrage verknüpft ist, somit also schon Ergebnisse während des Routings erziehlt werden könnnen.
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: DHT Vorschläge für Indizierung

Beitragvon Orbiter » Fr Mär 13, 2009 3:35 pm

das hört sich alles nicht schlecht an, aber du wirst sicherlich verstehen das wir nicht eine über Jahre gewachsene Methodik umschmeissen, weil du sagst 'mach doch mal was anderes'. An deinem Vorschlag hängt ja ein ganzes Projekt. Du muss wissen wie ein Index-Fragment aussieht, das du verschickst, wie du es aus dem Index auslöst und in dem Zielpeer integrierst. Und noch viele andere Fragen wirst du lösen müssen. Wenn dich das so fasziniert, dann fang doch einfach an: Nimm einen Indexierer, eine p2p-Verwaltung, eine Datenbank, einen Webserver, einen Crawler, Parser und noch viel mehr, und baue es um die Methodik herum. Ich schlage das vor, weil ich keine Chance sehe, hier was in YaCy umzubauen, aber dir auch die Idee nicht mit Argumenten vermiesen will. Es gibt sicherlich viele Dinge die man in YaCy hätte besser machen können. Vielleicht mit mehr Standard-Komponenten anfangen: tomcat, lucene, mysql etc. Ein total-Umbau kommt hier aber für mich nicht in Frage. Deswegen ist aber eine andere Idee nicht schlecht. Mach mal!
Orbiter
 
Beiträge: 5793
Registriert: Di Jun 26, 2007 10:58 pm
Wohnort: Frankfurt am Main

Re: DHT Vorschläge für Indizierung

Beitragvon wobble » Fr Mär 13, 2009 5:49 pm

@Orbiter ich verstehe deine Position voll und ganz. Ich erwarte auch überhaupt nicht, dass du irgendwas dafür implementierst. Es gibt bestimmt genug Baustellen. Wenn, setze ich mich selbst ran und versuche das zu bauen, vlt. als zusätliche Funktion für yacy (das erscheint mir als sinnvoller als andere auch neu zu bauen). Bevor ich mich aber an sowas ransetze, will ich natürlich erstmal wissen, ob das was ich mir vorstelle wirklich sinnvoll ist oder ob andere auch noch gute Ideen dazu haben. Deswegen der Post.
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: DHT Vorschläge für Indizierung

Beitragvon wobble » Sa Mär 28, 2009 10:33 am

ich hab jetzt mal selber ne test-implementierung von meiner Idee gamacht. Meine aktuelle implementierung ist noch recht langsam, vermutlich kann man die auch noch um einiges verbessern, aber mittlerweise glaube ich, dass meine Idee nicht wesentlich besser sein kann als die aktuell implementierte. Somit werde ich da keinen weiteren Entwicklungsaufwand hineinstecken.

Ihr speichert ja den lokalen Index als Tabelle. Wieso habt ihr den ganzen kram nochmal neu implementiert und keine schon existierende Datenbank, wie MySQL benutzt? Ich bin zwar selber kein Datenbanken-Experte, aber das klingt jedenfalls wie ein typischer Datenbank-Fall.
wobble
 
Beiträge: 19
Registriert: Do Mär 12, 2009 1:09 am
Wohnort: Berlin

Re: DHT Vorschläge für Indizierung

Beitragvon PCA42 » Sa Mär 28, 2009 1:14 pm

So wie ich das mitbekommen habe, ist das getestet worden. Aber für einen speziellen Anwendungsfall sollte immer eine spezielle Datenbank-Implementierung in Sachen Performance und Resourcen-Verbrauch optimal sein. Solange wie ich hier schon Yacy teste, ist nach meiner Meinung einem Menge an Programmieraufwand in die Datenbank und die Strukturen gesteckt worden. Und der kann hat sich eindeutig gelohnt.

Btw: Gibt es eigentlich eine Datenbank, die auch auf allen Plattformen wie Java läuft?
PCA42
 
Beiträge: 621
Registriert: Mi Jan 23, 2008 4:19 pm
Wohnort: @Home

Re: DHT Vorschläge für Indizierung

Beitragvon Low012 » So Mär 29, 2009 10:49 am

Habe ich noch nie benutzt, aber kommt AFAIK mit den aktuellen Sun JDKs: http://developers.sun.com/javadb/
Low012
 
Beiträge: 2214
Registriert: Mi Jun 27, 2007 12:11 pm


Zurück zu Wunschliste

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 1 Gast

cron