world-federation-of-advertisers / cardinality_estimation_evaluation_framework

Evaluation framework and methods for estimating cardinalities of groups of sets
Apache License 2.0
22 stars 9 forks source link

Fix a bug in geometric noiser #97

Closed pasin30055 closed 4 years ago

pasin30055 commented 4 years ago

If I'm not mistaken, it seems like the current way the geometric noiser is implemented (via rounding the laplace r.v.) is incorrect. For example, if sensitivity = epsilon = 1, then the geometric mechanism would put a mass of (1 - 1/e) / (1 + 1/e) = 0.462 at zero noise. However, the rounded laplace has mass of CDF(0.5) - CDF(-0.5) = 0.393 at zero. This change should fix this issue. (Note that the fix will result in smaller noise in expectation compared to before.)