diff options
author | antirez <antirez@gmail.com> | 2014-03-31 15:41:38 +0200 |
---|---|---|
committer | antirez <antirez@gmail.com> | 2014-03-31 15:41:38 +0200 |
commit | ec1ee66256a7fa05d6cd4ea0002c309b4fe238a9 (patch) | |
tree | 76e993806642f7ec15bf3323604fdf59666f1115 | |
parent | f2277475b2e6b165527866a8923a64d6862059e3 (diff) | |
download | redis-ec1ee66256a7fa05d6cd4ea0002c309b4fe238a9.tar.gz |
HyperLogLog apply bias correction using a polynomial.
Better results can be achieved by compensating for the bias of the raw
approximation just after 2.5m (when LINEARCOUNTING is no longer used) by
using a polynomial that approximates the bias at a given cardinality.
The curve used was found using this web page:
http://www.xuru.org/rt/PR.asp
That performs polynomial regression given a set of values.
-rw-r--r-- | src/hyperloglog.c | 29 |
1 files changed, 18 insertions, 11 deletions
diff --git a/src/hyperloglog.c b/src/hyperloglog.c index 70dfef2f2..9721205d2 100644 --- a/src/hyperloglog.c +++ b/src/hyperloglog.c @@ -339,7 +339,7 @@ int hllAdd(uint8_t *registers, unsigned char *ele, size_t elesize) { uint64_t hllCount(uint8_t *registers) { double m = REDIS_HLL_REGISTERS; double alpha = 0.7213/(1+1.079/m); - double E = 0, linearcounting_factor; + double E = 0; int ez = 0; /* Number of registers equal to 0. */ int j; @@ -407,17 +407,24 @@ uint64_t hllCount(uint8_t *registers) { /* Muliply the inverse of E for alpha_m * m^2 to have the raw estimate. */ E = (1/E)*alpha*m*m; - /* Use the LINEARCOUNTING algorithm for small cardinalities. Note that - * the HyperLogLog paper suggests using this correction for E < m*2.5 - * while we are using it for E < m*3 since this was verified to have - * better median / max error rate in the 40000 - 50000 cardinality - * interval when P * is 14 (m = 16k). - * - * However for other values of P we resort to the paper's value of 2.5 - * since no test was performed for other values. */ - linearcounting_factor = (m == 16384) ? 3 : 2.5; - if (E < m*linearcounting_factor && ez != 0) { + /* Use the LINEARCOUNTING algorithm for small cardinalities. + * For larger values but up to 72000 HyperLogLog raw approximation is + * used since linear counting error starts to increase. However HyperLogLog + * shows a strong bias in the range 2.5*16384 - 72000, so we try to + * compensate for it. */ + if (E < m*2.5 && ez != 0) { E = m*log(m/ez); /* LINEARCOUNTING() */ + } else if (m == 16384 && E < 72000) { + /* We did polynomial regression of the bias for this range, this + * way we can compute the bias for a given cardinality and correct + * according to it. Only apply the correction for P=14 that's what + * we use and the value the correction was verified with. */ + double bias = 5.9119*1.0e-18*(E*E*E*E) + -1.4253*1.0e-12*(E*E*E)+ + 1.2940*1.0e-7*(E*E) + -5.2921*1.0e-3*E+ + 83.3216; + E -= E*(bias/100); } /* We don't apply the correction for E > 1/30 of 2^32 since we use * a 64 bit function and 6 bit counters. To apply the correction for |