world-federation-of-advertisers / cardinality_estimation_evaluation_framework

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

Uakyol/stratified sketch noise #51

Closed uakyol closed 4 years ago

uakyol commented 4 years ago

Here is the second part of the stratified sketch where we introduce noising. We introduce a epsilon_split parameter to split the privacy budget into two parts: For 1+ sketch and other sketches.

   We support creation of 1+ sketch for 2 scenerios :
     1) 1+ sketch is created from the underlying exact set directly. Here we
     noise 1+ sketch with epsilon = (self.epsilon * self.epsilon_split).

     2) 1+ sketch is created from the union of all other frequencies. Here
     we noise 1+ sketch with epsilon = self.epsilon

  These two scenarios are controlled with the epsilon_split parameter. If
  epsilon_split = 0, then do scenario 1 otherwise do scenario 2.
AaronRanAn commented 4 years ago

Flagging that there's still an unresolved question from Craig.