Hi

Aber wenn man dann etwas zu hektisch reagiert ist natürlich alles weg.

so wars.

Du verfügst über eine Statistik der Forumssuche in derart hoher Auflösung? Kommen da andere auch ran?

hehehe ich extrapoliere da mein verhalten, kann natürlich auch sein das 90% der Leute auf anhieb perfekte Queries reinhauen und sofort zufrieden sind... (ich glaubs nicht)

Das ist nicht sonderlich sinnvoll, da die zweite Hashtabelle ebenfalls unter Kollisionen leiden wird. Wie regelst Du die?

So wie du es gewohnt bist als geschlossenen Hash. Ist die Zelle (falsch) belegt sucht eine kluge Methode ne neue.

BTW: Du benötigst für den ganzen Schisselamäng nur eine einzige ordentliche Hashfunktion, nicht mehr. Auch wenn die Hashtabellen optisch als zusammengehörig erscheinen, so sind sie doch völlig unabhängig und Du kannst einen einmal mühselig errechneten Hashwert vollständig wiederverwenden.

??? na eben nicht! Seien h=k die zugehörigen Fkten, für gleichmächtige Hashes H,K. Die k(W) berechne ich ja jeweils nur für die Wi der Kollisionen in H, d.h. h(W1)=h(W2). Ich hätte dann in K einen GAU von Kollision, wo alle k(Wi) alle auf den gleichen Wert abgebildet werden. Die Fkten müssen sehr wohl unabhängig sein, und zwar bewiesenermaßen (!) um performant zu sein.

Jetzt suche ich ein Wort W.

Fall 1 (Treffer): Ist das Schlüsselwort von S(H(W))=W habe ich gewonnen und erhalte eine Liste L(H(W)) aller Postings die W enthalten.

Woher weißt Du das?

Auf Assemblerebene? Belegte Zellen enthalten einen Pointer auf eine Datenstruktur der Form  (Schlüsselwort, *Post1, *Post2, *Post3,...)

Fall 2 (Kollision): Ich muss ich auf die Platte zugreifen und suche W im zugehörigen Hash K(H(W)).

I/O ist als genauso teuer anzusehen, wie ein DB-Anfrage. Dieser Teil der Übung ist also zweckfrei, direkte Anfage an DB wäre günstiger.

kann sein, aber die DB braucht ja auch GB-weise Metadaten, sonst würd sie ja schon laufen. Ausserdem bin ich ziemlich sicher das die DB mit ihrer Binären Suche viel häufiger auf die Platte zugreift.

Obige Hashtabelle wäre sehr günstig, wenn alle Anfragen Einwortanfragen wären.

Einwortanfragen? Du meinst wenn der Query nur aus einem Wort besteht?

Bei Mehrwortanfragen wäre jedes Wort einzeln zu prüfen. Gut, das ist seltenst viel, das würde sich wahrscheinlich auch noch lohnen. Phrasensuche wäre aber schon schwieriger.

Wieso seltenst? Die Schnittmenge der Postinglisten muss halt gebildet werden. (gleich kommt sowas wie geordnete Listen dafür nicht optimal sind ... geschenkt ;-)

Phrasensuche wäre aber schon schwieriger.

Natürlich, hier gehts nur um einzelne ganze Wörter.
Phrasensuche reicht im ersten Ansatz, so wie Daniela es auch plant.

Zudem ist diese Technik auf die Serverseite beschränkt.

Klar einen zweistufigen Hash brauche ich in JS nicht, weil dort sowieso alles (transparent) im RAM ist.

...obwohl - perverse Ideeee - eine Anwendung wäre dann die K-Hashes per HTTP in einem Popup anzufordern. *fg* Dann könnte man die Selfsuche auch in JS realisieren hehehe...

Ein Bloomfilter zwischen Eingabe und Cache macht da deutlich mehr Sinn.

Hab gerade mal bloomfilter http://en.wikipedia.org/wiki/Bloom_filterüberflogen. Durchaus faszinierend, aber wozu willst du den hier einsetzen? Teilstringsuche???

(im Vertrauen, das alles hab ich nie studiert, Theorie der Hashes kenn ich aus nem CT-Artikel vor 5 Jahren, auch Herrn Pearson musste ich erst nachschlagen, lerne momentan gut dazu :)

2. (Posting) Für jedes neue Posting müssen pro enthaltenem Wort die Liste L(W) um die Refernez auf das neue Posting erweitert werden.

Wie ist dies Liste implementiert?

Erstmal trivial aufsteigend linear sortiert. Brächte Vorteile wenn man     nur die Differenzen abspeichern muß, desto mehr Listen passen ins RAM.

Diese Reorganisation dürfte aber sehr selten vorkommen, weil das Vokabular des Forums nicht so schnell wächst.

Davon kannst Du nicht ausgehen, eher davon ds es zwischenzeitlich heftige Sprünge geben wird. Es muß nur eine andere Programmiersprache modern werden, ja, nur ein kurzes Listing in einer anderen Sprache würde einen guten Hub ergeben.

Mensch, aber selbst wenn, sorry ... wenn das Vokabular sich verdoppelte, müssten halt alle K-Hashes es auch werden. Das sind Sekunden.

Also ich halt jede Wette das der Zuwachs an Vokabeln des Forums über die Jahre abgeflacht ist.

Nein, Du brauchst nur eine einzige Hashfunktion, da alle Hastabellen in Deinem Gedankenexperiment unabhängig sind.

Eben nicht, s.o.

Ich hoffe das grobe Konzept einigermaßen rübergebracht zu haben,

Also um ehrlich zu sein ...
Wie wäre es mit einem kurzem Proof-of-Concept?

Nur der Algo schnell in JS realisiert wie oben beschrieben?
Hmm das könnte ich sogar gut recyclen...

Gut, ich bräuchte 2 Sätze Hashfkten zu einer vorgegebenen Bitlänge i, h_i, und k_ij wobei zu jeder bitlänge i,j die h_i und k_ij paarweise unabhängig sind.

(Für den PoC reicht auch ein Paar h, k unabhängig und Vokabular kleiner 2^(i+j))

Wenns die gibt, dann klappts auch. (ich könnt jetzt suchen, aber du schüttelst das doch aus dem Ärmel, oder :)

Insbesondere ist wichtig wie am besten Daten auf der Platte organisiert und darauf zugegriffen wird,

Das solltest Du dem Dateisystem überlassen, die modernen wie z.B. ReiserFS sind da kaum zu überbieten. Du kannst einafch schreiben, den

Rest übernimmt das FS.

Wenn ich damit performant auf Zellen der K-Hashes zugreifen kann, gerne.

ich denke die DB arbeitet da schon ziemlich effizient.

Eben.

ja aber bei euren Worstcase-Szenarien geht die DB viel schneller in die Knie. Die hier skizierte Methode kannst du auf Servern mit jedem RAM/HD-Szenario realisieren, der auch Michaels Vollindex schlucken kann.

Die Bäume einer DB sind doch auf viel generellere Anforderungen hin optimiert, die hier gar nie auftreten werden.  Z.B. müssen hier nicht täglich Millionen Postings eingetragen werden oder Rollbacks gefahren werden und und und ...

Tschau
  Rolf