Das Problem ist einfach: Ich muss die optimale Strategie finden, um genaue HyperLogLog-Vereinigungen basierend auf Redis 'Darstellung zu implementieren - dies beinhaltet die Behandlung ihrer spärlichen / dichten Darstellungen, wenn die Datenstruktur zur Verwendung an anderer Stelle exportiert wird.
Es gibt zwei Strategien, von denen eine viel einfacher erscheint. Ich habe mir die tatsächliche Redis-Quelle angeschaut und ich habe ein paar Probleme (nicht groß in C, ich) herauszufinden, ob es besser ist, aus einer Präzisions- und Effizienzperspektive ihre eingebauten Strukturen / Routinen zu verwenden oder meine eigenen zu entwickeln . Für was es wert ist, bin ich bereit, Raum und bis zu einem gewissen Grad Fehler (stdev + -2%) im Streben nach Effizienz mit extrem großen Mengen zu opfern.
Bei weitem die einfachste der beiden - im Wesentlichen würde ich nur die verlustfreie Vereinigung (PFMERGE) in Kombination mit diesem Prinzip verwenden, um eine Schätzung der Überlappung zu berechnen. Tests scheinen zu zeigen, dass dies in vielen Fällen zuverlässig funktioniert, obwohl ich Probleme habe, die Effizienz und Genauigkeit in der Praxis genau zu kennen (in einigen Fällen können Fehler von 20-40% auftreten, was in diesem Anwendungsfall inakzeptabel ist).
Grundsätzlich:
%Vor%oder, im Falle mehrerer Sätze ...
%Vor%scheint in vielen Fällen mit guter Genauigkeit zu funktionieren, aber ich weiß nicht, ob ich ihm vertraue. Während Redis viele eingebaute Low-Cardinality-Modifikatoren hat, die entworfen wurden, um bekannte HLL-Probleme zu umgehen, weiß ich nicht, ob das Problem der wilden Ungenauigkeit (unter Verwendung von Einschluss / Ausschluss) immer noch mit Gruppen hoher Disparität in der Größe vorhanden ist ...
Dieser Weg scheint interessanter zu sein, aber ein Teil von mir fühlt sich so an, als würde er sich mit einigen der vorhandenen Optimierungen von Redis überschneiden (dh ich implementiere meinen eigenen HLL-Algorithmus nicht von Grund auf neu).
Mit diesem Ansatz würde ich eine zufällige Auswahl von Bins mit einem MinHash-Algorithmus verwenden (ich glaube nicht, dass eine LSH-Implementierung den Aufwand wert ist). Dies wäre eine separate Struktur, aber indem Sie minhash verwenden, um den Jaccard-Index der Mengen zu erhalten, können Sie dann effektiv die Unionskardinalität mit diesem Index für eine genauere Zählung multiplizieren.
Problem ist, ich bin nicht sehr versiert in HLL und während ich gerne in das Google-Papier graben würde, brauche ich eine praktikable Implementierung in kurzer Zeit. Es ist wahrscheinlich, dass ich einige grundlegende Überlegungen zu den vorhandenen Optimierungen von Redis überblicke, oder aber zu dem Algorithmus selbst, der rechnerisch billige Schnittpunktschätzungen mit ziemlich laschen Vertrauensgrenzen erlaubt.
also, meine Frage:
Wie kann ich am effektivsten eine rechnerisch günstige Schätzung von N riesigen (Milliarden) Mengen mit redis erzielen, wenn ich bereit bin, Platz zu opfern (und zu einem kleinen Grad , Genauigkeit)? ?
Lesen Sie diese Zeitung vor einiger Zeit. Wird wahrscheinlich die meisten Ihrer Fragen beantworten. Inklusionsprinzip verschmilzt zwangsläufig Fehlerränder mit einer großen Anzahl von Sätzen. Min-Hash-Ansatz wäre der Weg zu gehen.
Tags und Links redis hash hashtable hyperloglog minhash