Marginal histograms?

[jonasz]

Hi Charlie,

Thanks for clarifying #183. This leads me to a follow up question about adding support for "marginal histograms".

The number of non-negligible partitions ((adv, pub) pairs per time window) will easily be in the tens of thousands, potentially higher. There's also going to be a long tail of partitions with just a couple contributions, which sum to a significant fraction of all contributions.

Let's say I'd like to calculate some "global" aggregate, for example a "global spend" - would I have to add up the values from each partition? If so, the noise from each partition would accumulate in the final global aggregate, which is unfortunate.

I was wondering, would you say the query model could support "marginal histograms" as well? So that I could say "I'd like to query for key=12515, across all publishers and advertisers", or "I'd like to query for key=1414 for all publishers and advertiser=exampleadvertiser.com"? This would be very useful, if we could avoid the accumulated-noise problem.

Best regards,
Jonasz

[csharrison]

Looking into this.

[csharrison]

Looked into this and I think this should be OK privacy-wise as long as each histogram contribution is still only a function of each single (adv, pub) pair, and that contribution takes from the privacy budget of that pair which is the case in the current document.

[csharrison]

This should be supported in the aggregation service. Please re-open if there's any further issues here.