-
Notifications
You must be signed in to change notification settings - Fork 2
/
fm85Confidence.c
146 lines (130 loc) · 4.72 KB
/
fm85Confidence.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
// Copyright 2018, Kevin Lang, Oath Research
/*******************************************************/
#include "common.h"
#include "fm85.h"
#include "iconEstimator.h"
/*******************************************************/
// ln 2.0
double iconErrorConstant = 0.693147180559945286;
// 1, 2, 3, // kappa
Short iconLowSideData [33] = { // Empirically measured at N = 1000 * K.
6037, 5720, 5328, // 4 1000000
6411, 6262, 5682, // 5 1000000
6724, 6403, 6127, // 6 1000000
6665, 6411, 6208, // 7 1000000
6959, 6525, 6427, // 8 1000000
6892, 6665, 6619, // 9 1000000
6792, 6752, 6690, // 10 1000000
6899, 6818, 6708, // 11 1000000
6871, 6845, 6812, // 12 1046369
6909, 6861, 6828, // 13 1043411
6919, 6897, 6842, // 14 1000297
}; // lgK numtrials
// 1, 2, 3, // kappa
Short iconHighSideData [33] = { // Empirically measured at N = 1000 * K.
8031, 8559, 9309, // 4 1000000
7084, 7959, 8660, // 5 1000000
7141, 7514, 7876, // 6 1000000
7458, 7430, 7572, // 7 1000000
6892, 7141, 7497, // 8 1000000
6889, 7132, 7290, // 9 1000000
7075, 7118, 7185, // 10 1000000
7040, 7047, 7085, // 11 1000000
6993, 7019, 7053, // 12 1046369
6953, 7001, 6983, // 13 1043411
6944, 6966, 7004, // 14 1000297
}; // lgK numtrials
/*******************************************************/
// sqrt((ln 2.0) / 2.0)
double hipErrorConstant = 0.588705011257737332;
// 1, 2, 3, // kappa
Short hipLowSideData [33] = { // Empirically measured at N = 1000 * K.
5871, 5247, 4826, // 4 1000000
5877, 5403, 5070, // 5 1000000
5873, 5533, 5304, // 6 1000000
5878, 5632, 5464, // 7 1000000
5874, 5690, 5564, // 8 1000000
5880, 5745, 5619, // 9 1000000
5875, 5784, 5701, // 10 1000000
5866, 5789, 5742, // 11 1000000
5869, 5827, 5784, // 12 1046369
5876, 5860, 5827, // 13 1043411
5881, 5853, 5842, // 14 1000297
}; // lgK numtrials
// 1, 2, 3, // kappa
Short hipHighSideData [33] = { // Empirically measured at N = 1000 * K.
5855, 6688, 7391, // 4 1000000
5886, 6444, 6923, // 5 1000000
5885, 6254, 6594, // 6 1000000
5889, 6134, 6326, // 7 1000000
5900, 6072, 6203, // 8 1000000
5875, 6005, 6089, // 9 1000000
5871, 5980, 6040, // 10 1000000
5889, 5941, 6015, // 11 1000000
5871, 5926, 5973, // 12 1046369
5866, 5901, 5915, // 13 1043411
5880, 5914, 5953, // 14 1000297
}; // lgK numtrials
/*******************************************************/
double getIconConfidenceLB (FM85 * sketch, int kappa) {
if (sketch->numCoupons == 0) return 0.0;
int lgK = sketch->lgK;
long k = (1LL << lgK);
assert (lgK >= 4);
assert (kappa >= 1 && kappa <= 3);
double x = iconErrorConstant;
if (lgK <= 14) x = ((double) iconHighSideData[3*(lgK-4) + (kappa-1)]) / 10000.0;
double rel = x / (sqrt((double) k));
double eps = ((double) kappa) * rel;
double est = getIconEstimate (lgK, sketch->numCoupons);
double result = est / (1.0 + eps);
double check = (double) sketch->numCoupons;
if (result < check) result = check;
return (result);
}
double getIconConfidenceUB (FM85 * sketch, int kappa) {
if (sketch->numCoupons == 0) return 0.0;
int lgK = sketch->lgK;
long k = (1LL << lgK);
assert (lgK >= 4);
assert (kappa >= 1 && kappa <= 3);
double x = iconErrorConstant;
if (lgK <= 14) x = ((double) iconLowSideData[3*(lgK-4) + (kappa-1)]) / 10000.0;
double rel = x / (sqrt((double) k));
double eps = ((double) kappa) * rel;
double est = getIconEstimate (lgK, sketch->numCoupons);
double result = est / (1.0 - eps);
return (ceil(result)); // widening for coverage
}
/*******************************************************/
double getHIPConfidenceLB (FM85 * sketch, int kappa) {
if (sketch->numCoupons == 0) return 0.0;
int lgK = sketch->lgK;
long k = (1LL << lgK);
assert (lgK >= 4);
assert (kappa >= 1 && kappa <= 3);
double x = hipErrorConstant;
if (lgK <= 14) x = ((double) hipHighSideData[3*(lgK-4) + (kappa-1)]) / 10000.0;
double rel = x / (sqrt((double) k));
double eps = ((double) kappa) * rel;
double est = getHIPEstimate (sketch);
double result = est / (1.0 + eps);
double check = (double) sketch->numCoupons;
if (result < check) result = check;
return (result);
}
double getHIPConfidenceUB (FM85 * sketch, int kappa) {
if (sketch->numCoupons == 0) return 0.0;
int lgK = sketch->lgK;
long k = (1LL << lgK);
assert (lgK >= 4);
assert (kappa >= 1 && kappa <= 3);
double x = hipErrorConstant;
if (lgK <= 14) x = ((double) hipLowSideData[3*(lgK-4) + (kappa-1)]) / 10000.0;
double rel = x / (sqrt((double) k));
double eps = ((double) kappa) * rel;
double est = getHIPEstimate (sketch);
double result = est / (1.0 - eps);
return (ceil(result)); // widening for coverage
}
/*******************************************************/