Hi,

Ja, von unserer Diskussion hier, warum?

Hmm, also dass es klappt ist IMHO klar, da es nur eine Verallgemeinerung von Hashes darstellt. Für mich bleibt nur offen, wie aufwendig die Hashfkt und das I/O kommen.

Als Hashfunktion wird normalerweise ein kryptographischer Hash vorgeschlagen, Mitzenmacher hat z.B. DES genommen. Aufgrund der guten Verteilung der Bits im Hashwert selber kann man den dann tatsächlich "teilen".
Ich wollte MD5 nehmen, dafür gibt es ja bereits eine Javascriptimplementation.
Man könnte aber auch tatsächlich 4 einfache Hashfunktionen nehmen, da die Strings ja nur sehr kurz sind (über 30 Zeichen werden wohl kaum da rauskommen, wenn man Phrasen ignoriert. Aber nur, um mal eine Zahl zu nennen). Da kann dann man schon viermal drübergehen und ist evt immer noch biliger, als MD5.

Aber die Hashfunktionen sind vomprogrammiertechnischem Standpunkt her ziemlich beliebig autauschbar, das ist ein Sache von Minuten.

Wenn da auch noch eine erlaubte Fehlermarge hineinspielt wird's mir zu komplex. Das könnte ich vielleicht noch implementieren, aber mit Sicherheit nicht mehr formal untermauern. Und empirische Beweisführung ist bei Mathematikern ja schon deutlich mehr als einfach nur verpönt, oder?

Wär ja nicht empirisch sondern statistisch!

Nein, beim mir wäre es empirisch, statistisch wäre mir schon zu kompliziert ;-)

Im übrigen sind viele Hashfkt AFAIK nur empirisch durch Tests untermauert.

Ja, das ist mir auch aufgefallen. Mir ist sogar keine einzige bekannt, die tatsächlich berechnet wurde. Weder a priori noch a posteriori.

Hmm ja aber worauf ich hinaus will:

Wenn man die gleiche Hashfktnen und die gleiche Filterlänge hat reicht es die  Filter aller Suchwörter miteinander zu schneiden um eine Abschätzung der Schnittmenge zu erhalten, im Extrem ist leerer Schnitt =erfolglose Suche.

Ja, könnte sich evt lohnen, insbesondere für die Phrasensuche. Braucht aber auch eine Menge Speicher, denn es wäre hier ein Bloomstring pro Liste erforderlich. Einfacher wäre es einen einzige Bloomstring für alle Suchwörter zu basteln, so das "not found" die DB gar nicht mehr belastet.

Habe ich nun eine Liste mit 10000 Treffern ("Javascript") und eine mit 20 kommt man nur schwerlich mit nur einer Filterlänge aus.

Deshalb braucht man ja auch soviel Platz dafür.

Aber wenn man sich ein wenig an die 400 gecachten Seiten hält, kann man ganz gut mit fixen Werten arbeiten, die dann bei Bedarf händisch geändert werden. Sieht dann zwar alles wenig elegant aus, aber funktioniert.

Ehrlich gesagt, ich halte nen extra Cache für überflüssig wenn man schon den RAM-Hash H dafür hat. Obwohl wir verschiedene Sachen cachen, würd ich dann lieber RAM für die Posting-Listen aufwenden.

Wie bereist vorgerechnet ist der Platzverbrauch nicht sonderlich hoch und mit vollständigem Caching sparst Du I/O auch vollständig ein. Manmüßte die genauen Zahlen haben, wieviele Leute überhaupt weiterblättern, und wieviele Prozent der Suche die vorgeschlagenen 400 Suchbegriffe ausmachen. Ohne diese Zahlen natürlich eine gewagte Hypothese, aber ich nehme doch an, das ich mit diesen 400 Begriffen schon so um die 95% abdecke und kaum einer weiterblättert.

Andere Idee:

Wenn schon Lastverteilung gewünscht, dann lass doch gleich die Hashfunktionen des genesteten Hashes H x K_i auf dem Client berechnen.

(D)DoS is' g'fährlich, wie der bayerischer Programmierer hier anmerken würde.

Interessant, frisst JS von Haus aus Base64 Codierte Daten?
Nein, leider nicht jeder. Ist aber eine sehr billige Funktion, hüben wie drüben. Sind ja nur ein paar Bytes.

Um es mit JS zu decodieren? Lohnt sich das wirklich wenn ich den JS-Source auch gezipt ausliefern kann?

Achso, nein: ich muß ja verschiedene Bytes maskieren, da kann ich dann auch billiger gleich alle mit base64 maskieren. Ist dann zwar 30% länger, aber das macht den Hasen auch nicht mehr fett und fällt bei Auslieferung mit gzip eh wieder unter den Tisch.

Was mich aktuell noch von einer Implementierung abhält ist die Tatsache dass die Aufgabe der Teilstringsuche noch nicht elegant gelöst ist. Was hilfts in nanosec
zu wissen wo überall ganze Wörter wie "Javascript" auftauchen, wenn ich die Platte nach Wörtern durchsuchen muss, die "Java" enthalten könnten?!?

Für Teilstringfragen, vor allem solche "gierigen", ist das halt nicht geeignet, dafür gibt's dann andere Methoden.
Es ist nunmal ohne genaue Analysen der Suchanfragen nicht viel zu machen. Eine generelle, sozusagen optimale Lösung dürfte nicht existieren.

so short

Christoph Zurnieden