Hi,

Also ich Legastheniker dachte auch dass sich die Tauben mit dg schreiben, es braucht also kein "Sorry". :)

Allerdings bleibt das googlen immer noch dürftig.

Ja, leider. Aber ich schau mal, was sich anderweitig so verbirgt. Zur Not bastel ich mal ein Beispiel.

Momentmal 1: Du versuchst bereits einen "Durchschnitt von n Listen" Algo mit Bloom Filtern zu realisieren?

Nein, da keine Fehler genehmigt worden sind.
Genehmigt? Sprichst du von einem konkreten Projekt?

Ja, von unserer Diskussion hier, warum?
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ä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.

Ja, soviel geht natürlich (sonst hätte ich diese Idee auch sofort verworfen), aber es läßt sich von C aus nicht ganz 1:1 übersetzen. Mit ein wenig Mühe geht es aber doch und das meinte ich damit. Es sollte nach Möglichkeit jedesmal der gleiche Code sein, damit das Managment nicht ausufert.

Du kannst fehlende Funktionen oft gut mit Arrays realisieren. Z.B setBit(x) mit einem Array aus 32 Langwörtern die per OR verknüpft werden.

Zum Beipiel, ja.
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.

Indem ich etwas über einen KiB Bitstring in etwas unter eine KiB Bitstring komprimiere.
http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/cbf.pdf

Also neeee, da bin ich skeptisch. Die Kompressionsrate hochzutreiben in dem man die Zahl der Hashfkten reduziert ist doch reichlich ins Knie geschossen (habs nur überflogen aber trotzdem!).

Nicht nur übefliegen, dsa war nämlich auch mein Fehler. Das funktioniert tatsächlich. Vorteil liegt aber weniger in der reduzierten Größe des resultierenden Bloomstrings - wird aber natürlich gerne mitgenommen, Bandbreite kostet schließlich Geld - sondern in der Reduktion der Anzahl der nötigen Hashfunktionen.
Ist für unseren Fall wenig von Belang, aber trotzdem recht interessant.

Da wähl ich die Parameter doch lieber gleich passend oder modifiziere das Konzept dahingehend dass ich von vornherein mit weniger Hashfkt weniger Platz brauche.

Genau das tut ja diese Kompression.

Bitstream geht ja schlecht; bleibt nur Text! Und den würd ich sowieso gzippt ausliefern.

Ja, Base64-Codiert muß der natürlich werden, klar.

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.

Da Du das ja kaum C&P von irgendwoher geklaut hast, hast Du da Arbeit reingesteckt, dafür muß ich mich doch bedanken, oder nicht?

Sagen wir mal ich hab Rechthaberei und Sturheit reingesteckt, dass kann ein ziemlicher Fluch sein, allem auf den Grund gehen zu wollen. ;|

Ja, das kann ich gut nachvollziehen.
Sehr gut sogar.

so short

Christoph Zurnieden