Hi Christoph,

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.

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!

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

Wäre aber bei unsortierten Listen eine gute Möglichkeit, wenn geringe Fehler erlaubt sind oder nur danach gesucht wird, ob _keine_ Schnittmenge existiert.

Ja, bei unseren Postinglisten könnte man mit _zusätzlichen_ Bloomfiltern vielleicht sogar den durchschnittlichen Aufwand nochmals senken. Das Bloomfilterkonzept müsste allerdings scalierbar gemacht werden, da die Zahl der Einträge pro Liste ja nicht fix sind.

Muß nicht extra dazu gemacht werden, ist es ja schon in ausreichenden Grenzen. Die Fehlermarge steigt ja nicht so sonderlich steil, das man da nicht einiges verschmerzen könnte.

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.

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

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.

Und ob es sich lohnt 400 ganze HTML-Seiten im RAM zu halten, bezweifle ich, das kann aber letztlich nur eine Analyse der Useranfragen ergeben.

Andere Idee:

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

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?

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

Bye
 rolf