Suppression and seeding for star buckets

[yoid2000]

Let's briefly discuss suppression and seeding rules for star buckets.

I propose that there is no sql_seed for the start bucket. This in turn means that both the suppression decision and the noise addition are based on a single noise layer (Elm spec describes how to do this).

For suppression, I would like to avoid cases where the star bucket consists of a single suppressed bucket. This could sometimes happen because the single bucket uses a different noisy threshold when computed as the star bucket (two noise layers for the single bucket, one noise layer as the start bucket).

One way to avoid this is to simply have a rule that says that there must be at least two suppressed buckets in the star bucket.

Another would be to triple the values all three of the suppression parameters (low_thresh, low_mean_gap, sd_supp).

I slightly prefer the first way, but we should do whatever is simpler.

@edongashi @cristianberneanu @pdobacz

[cristianberneanu]

I propose that there is no sql_seed for the start bucket. This in turn means that both the suppression decision and the noise addition are based on a single noise layer (Elm spec describes how to do this).

I already commented on this in the paper review discussion. Special cases generate complexity and are a fertile ground for bugs.
We could either use a default seed for the star bucket or generate a regular bucket seed using * for the bucket labels. The latter is more consistent with the handling of regular buckets.

I slightly prefer the first way, but we should do whatever is simpler.

The first way is also simpler.

[yoid2000]

The idea of a default sql_seed = owh(salt, 0) is good. I'll update the Elm spec accordingly.

The idea of doing a regular bucket seed using * as the labels is also good. Let's assume this.

If there are no objections, let's make Cristian's comment as the answer...

[edongashi]

Do we want the same seed for any number of columns in the star bucket, i.e. does *, *, 15 and *, *, *, 15 have the same seed?

[yoid2000]

I understand the intent to be that the star bucket would be seeded the same way as a normal bucket, but with the exception that * is used as the column value. In normal bucket seeding, the column name is also used, so anything with three two columns versus three columns would be different by virtue of the column names.

[pdobacz]

Late to the party, and I may have missed something basic, but would there be a possibility of having sql_seed be derived from a concatenation of suppressed bucket_values, which comprise the star bucket?

This way, the sql_seed for the single suppressed bucket would be the same as the *-bucket, making the suppression and noise values the same. This could be even less of a "special handling" and would allow us to not introduce the "at least two suppressed buckets in the star bucket" rule at all.

So in detail as there's in elm.pdf:

gb_sql = h(column_name ,bucket_value, range_type ,range_param)

we turn this into

gb_sql = h(column_name , bvh(bucket_values), range_type ,range_param)

where the "bucket values hash" bvh function is (possibly not all the h hashes are necessary):

bvh = h(XOR(h(bucket_value_1), h(bucket_value_2), ...))

For normal buckets, the bucket values set is single element and bvh(bucket_values) is equivalent to current form of just bucket_value. For "single bucket *-buckets" we have the advantage of bvh being the same as the bucket contained within.

[yoid2000]

I don't see how this prevents us from having the rule of needing at least two suppressed bucket comprising the star bucket.

[pdobacz]

So I'm based on this:

This could sometimes happen because the single bucket uses a different noisy threshold when computed as the star bucket

if we ensure that this single bucket uses the same noisy threshold as the star bucket, the problem goes away, am I correct here?

So what I'm trying to achieve is to have the star bucket seeds coincide with the single suppressed bucket. If the seeds are the same, then the noisy thresholds are the same, and the star bucket is treated "the same" as the single suppressed bucket.

---

But having written that, I've now realized that this is equivalent to just not showing the "single bucket * bucket" manually. I guess my proposed solution isn't worth it then.

[yoid2000]

if we ensure that this single bucket uses the same noisy threshold as the star bucket, the problem goes away, am I correct here?

I see. Yes, I think you are right.

I guess my proposed solution isn't worth it then.

Perhaps so. It becomes a question mainly of what is simpler to implement, and for that Edon and Cristian would have to chime in.

This business of seeding is going to get much more complex once we start bringing in WHERE clauses and other things, by the way...we are going to have to revisit some of this in any event.

[cristianberneanu]

Requiring at least two suppressed buckets is simpler to understand and implement., so I would prefer that for the time being.

having sql_seed be derived from a concatenation of suppressed bucket_values, which comprise the star bucket

Your approach has the interesting property that the sql_seed for the star-bucket would change for different suppressed buckets.
I don't think this is needed in the current design, but it might be useful in the future, so let's keep it in the back of our mind for later.