redis HLL zu viele Fehlalarme

Question

HyperLOG log ein probablistic Algorithmus Nach dem redis HLL Dokument ist, könnten wir 0,81% der Fehler erhalten, aber ich bekomme Fehler wie 17-20%

Ich denke, es ist etwas falsch. Dies ist mein einfaches Perl-Testskript. Gibt es einen Fehler

#!/usr/bin/perl -w                                      
use Redis; 
my $redis = Redis->new(server=>'192.168.50.166:6379') or die; 
my $fp=0; 
my $HLL="HLL"; 

$redis->del($HLL); 
foreach my $i (1..10000) { 
    my $s1 = $redis->pfadd($HLL,$i); 
    if($s1 == 0){ 
    print "False positive on $i\n"; 
    $fp++; 
    } 
} 
print "count of false positives $fp\n"; 

Answer 1

HyperLogLog zum Zählen Unikate verwendet. Es kann eine große Anzahl von Elementen mit wenig Speicher zählen. Die zurückgegebene Kardinalität ist jedoch NICHT exakt, sondern angenähert mit einer standard error.

0,81% ist die standard error, NICHT die falsche positive. Für Ihre Instanz können Sie PFCOUNT HLL anrufen, um die ungefähre Anzahl der eindeutigen Elemente zu erhalten, die Sie in die HyperLogLog eingeben. Die zurückgegebene Nummer sollte im Bereich von [10000 * (1 - 0.81%), 10000 * (1 + 0.81%)] liegen.

PFADD gibt 1 zurück, wenn die geschätzte Kardinalität nach der Ausführung des Befehls geändert wird. Andernfalls wird 0 zurückgegeben. Es hat nichts mit false positive zu tun.

Es scheint, dass Sie eine Bloom Filter benötigen, die Ihnen sagen kann, ob ein Element bereits in einem Datensatz vorhanden ist, mit false positive. Sie können natürlich eine Bloom Filter mit Redis implementieren. Und dafür sollte es ein Open-Source-Projekt geben.