Hi,

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)

Oder die geben auf, wenn sie nicht sofort 'was finden und posten daraufhin im Forum.
Nein, ohne Daten ist es recht müßig über das Verhalten der Benutzer zu mutmaßen.

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.

Tja, das hatte ich befürchtet, das ist auch sehr schlecht vorstellbar. Also nochmal:
Stell Dir vor, Du hast eine Hashtabelle H mit 5 Löchern {a,b,c,d,e} und eine Funktion f(x), die alle Elemente einer Menge S gleichmäßig auf diese Löcher abbildet. Ist |S| größer als |H| dann kommt es zu Mehrfachbelegung, zu Kollisionen. Nun steht hinter jenen Löchern von H je eine weitere Hashtabelle H_i = {f,g,h,i,j}.
Zuerst wird jedes Loch in H gefüllt (wir setzen einmal eine optimale Verteilung der Hashwerte voraus), nach fünf Vorgängen erfolgt also die erste Kollision, sagen wir mal in a. Wir brauchen nun also eine Hashfunktion, die ein Element aus S in H_i packt. Was hindert uns nun daran, ebenfalls f(x) zu nehmen? Dadurch, das H voll ist, wird eine _neue_ Hastabelle genommen, wir fangen sozusagen bei 0 an. D.h.: wir können den alten Hashwert nehmen, der funktioniert für H_i genauso gut oder schlecht, wie für H. Vorausgesetzt natürlich, das |H| = |H_i|, aber das trifft in Deinem Beispiel ja zu.
Jetzt verstanden? Na, ich sehe noch zweifelnde Blicke ...
Bastel Dir einfach ein Beispiel, oder mal's Dir auf, das hilft mir auch mitunter.

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.

So funktioniert eine DB nicht, das ist da schon etwas geschickter geregelt. Wenn ich mein "endlich mal meine Boomarks aufräumen" nicht schon seit Ewigkeiten vor mir her schieben würde, könnte ich Dir jetzt auch ein paar gute Links anbieten, aber auf die Schnelle finde ich hier nix. Vielleicht hast ja Du Glück und einer der zwei-drei Mitleser hat welche parat?

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

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

Ein Begriff, ja. Muß natürlich nicht nur ein Wort sein.

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 ;-)

Schnittmenge bilden ist _sehr_ teuer. Noch teurer fast, als ein grep durch's Archiv. Wenn das sein muß, ist die ganze vorherige Optimierung für die Katz.
(Da es sortierte Listen bekannter Länge sind, könnte man die Schnittmengenbildung evt(!) auf nlogn runterbringen, aber auch nur als Best Case. Durchschnitt wäre n^2 und Worst case n^3. Mmh... nein, Worst Case käme gar nicht vor, oder?)

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???

Nein, sondern genau dafür, wofür das Dingen ursprünglich gedacht war: um auf einfache Weise nachschauen zu können, ob mit einer recht genau bestimmbaren Wahrscheinlichkeit etwas gecached wurde. Das ließe sich per Javascript realisieren und so würde jeder mit eingeschaltetem Javascript die Server-Belastung reduzieren können.

(im Vertrauen, das alles hab ich nie studiert,

Ich auch nicht, ist also kein Grund.

Theorie der Hashes kenn ich aus nem CT-Artikel vor 5 Jahren,

Gut, _das_ ist ein Grund.

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.

Warum nicht gleich als fertige Seite?

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

Das ist Microoptimierung, vergiss es schnell wieder.
(Du verbrauchst fast schon mehr Zeit diese Differenzen zu erstellen, als sie nachher gewinnen)

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

... und schon ist das RAM voll.

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

Ich setz' 'n Kasten Bier dagegen.

Wie wäre es mit einem kurzem Proof-of-Concept?

Nur der Algo schnell in JS realisiert wie oben beschrieben?

Zum Beipiel.

Hmm das könnte ich sogar gut recyclen...

Altruismus hatt ich auch nicht vorausgesetzt.

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 :)

CRC ist eine gute Möglichkeit, wenn Du die passenden primitiven Polynome n-ter Ordnung (n ist hier die Anzahl an Bits, also bei einem 16-Bit Hashwert brauchst Du ein gutverteiltes primitives Polynom 16ter Ordnung) wählst. Die sollten möglichst gut verteilt sein, dann kannst Du so einen CRC auch zum Hashen beutzen, auch wenn der dafür gar nicht vorgesehen ist. Leider hat sch noch kein Mathematiker die Mühe gemacht, ds soweit zu unetrsuchen, das dabei eine Funktion rauskommt, die so ein Polynom auf Anhieb finden kann, es gilt also leider T&E.

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.

Wie denn sonst?

ich denke die DB arbeitet da schon ziemlich effizient.

Eben.

ja aber bei euren Worstcase-Szenarien geht die DB viel schneller in die Knie.

Das wollen wir nicht hoffen, das dabei die DB in die Knie geht, aber es sind in bestimmten Fällen eben aufwendigerer Anfragen zu bearbeiten.

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

Skalierbarkeit hat hier wenig mit zu tun.

oder Rollbacks gefahren werden und und und ...

Wenn Du eine Funktion der DB nie brauchst, dann kannst Du sie auch einfach ausbauen. Aber das sind alles Kleinigkeiten, die ich auch wieder zur Mikrooptimierung zählen würde. Mit einer geschickten Datenstruktur erreichst Du da schon deutlich mehr. Selbst beim Caching würde ich vorher sorgfältig die Gewohnheiten der Sucher studieren, bevor ich mich vor meinen Lieblingseditor setzte.

so short

Christoph Zurnieden