|
56 | 56 | staticinlineuint8rho(uint32x,uint8b); |
57 | 57 |
|
58 | 58 | /* |
59 | | - * Initialize HyperLogLog track state |
| 59 | + * Initialize HyperLogLog track state, by bit width |
60 | 60 | * |
61 | 61 | * bwidth is bit width (so register size will be 2 to the power of bwidth). |
62 | 62 | * Must be between 4 and 16 inclusive. |
@@ -107,6 +107,52 @@ initHyperLogLog(hyperLogLogState *cState, uint8 bwidth) |
107 | 107 | cState->alphaMM=alpha*cState->nRegisters*cState->nRegisters; |
108 | 108 | } |
109 | 109 |
|
| 110 | +/* |
| 111 | + * Initialize HyperLogLog track state, by error rate |
| 112 | + * |
| 113 | + * Instead of specifying bwidth (number of bits used for addressing the |
| 114 | + * register), this method allows sizing the counter for particular error |
| 115 | + * rate using a simple formula from the paper: |
| 116 | + * |
| 117 | + * e = 1.04 / sqrt(m) |
| 118 | + * |
| 119 | + * where 'm' is the number of registers, i.e. (2^bwidth). The method |
| 120 | + * finds the lowest bwidth with 'e' below the requested error rate, and |
| 121 | + * then uses it to initialize the counter. |
| 122 | + * |
| 123 | + * As bwidth has to be between 4 and 16, the worst possible error rate |
| 124 | + * is between ~25% (bwidth=4) and 0.4% (bwidth=16). |
| 125 | + */ |
| 126 | +void |
| 127 | +initHyperLogLogError(hyperLogLogState*cState,doubleerror) |
| 128 | +{ |
| 129 | +uint8bwidth=4; |
| 130 | + |
| 131 | +while (bwidth<16) |
| 132 | +{ |
| 133 | +doublem= (Size)1 <<bwidth; |
| 134 | + |
| 135 | +if (1.04 /sqrt(m)<error) |
| 136 | +break; |
| 137 | +bwidth++; |
| 138 | +} |
| 139 | + |
| 140 | +initHyperLogLog(cState,bwidth); |
| 141 | +} |
| 142 | + |
| 143 | +/* |
| 144 | + * Free HyperLogLog track state |
| 145 | + * |
| 146 | + * Releases allocated resources, but not the state itself (in case it's not |
| 147 | + * allocated by palloc). |
| 148 | + */ |
| 149 | +void |
| 150 | +freeHyperLogLog(hyperLogLogState*cState) |
| 151 | +{ |
| 152 | +Assert(cState->hashesArr!=NULL); |
| 153 | +pfree(cState->hashesArr); |
| 154 | +} |
| 155 | + |
110 | 156 | /* |
111 | 157 | * Adds element to the estimator, from caller-supplied hash. |
112 | 158 | * |
|