search

WICG / attribution-reporting-api

Attribution Reporting API
https://wicg.github.io/attribution-reporting-api/
Other
367 stars 173 forks source link

Use bit search for max epsilon #1429

Closed giladbarkan-github closed 2 months ago

giladbarkan-github commented 2 months ago

Bit search can yield higher precision than binary search in constant time and avoid the use of a tolerance.

giladbarkan-github commented 2 months ago

Does Android use this algorithm in its implementation? If so, could we add some analogous deterministic test cases to make it easier to verify and reproduce the behavior here?

What do you think about adding a validation that adding anything in the double range to epsilon would result in too high info gain (still using random tests)? This would prove correctness.

apasel422 commented 2 months ago

Does Android use this algorithm in its implementation? If so, could we add some analogous deterministic test cases to make it easier to verify and reproduce the behavior here?

What do you think about adding a validation that adding anything in the double range to epsilon would result in too high info gain (still using random tests)? This would prove correctness.

Property-based testing is good, but I still think some deterministic test cases would be beneficial as well as they are more easily ported between implementations.

giladbarkan-github commented 2 months ago

Does Android use this algorithm in its implementation? If so, could we add some analogous deterministic test cases to make it easier to verify and reproduce the behavior here?

What do you think about adding a validation that adding anything in the double range to epsilon would result in too high info gain (still using random tests)? This would prove correctness.

Property-based testing is good, but I still think some deterministic test cases would be beneficial as well as they are more easily ported between implementations.

Android does not use an epsilon search presently. I'll add the extra validation, log some of its results and add those as deterministic.

giladbarkan-github commented 2 months ago

Property-based testing is good, but I still think some deterministic test cases would be beneficial as well as they are more easily ported between implementations.

Done.

csharrison commented 2 months ago

The bit search looks fine but why keep the binary search verison too?

giladbarkan-github commented 2 months ago

The bit search looks fine but why keep the binary search verison too?

I first thought it can help validate but what Andrew termed the "property" assertion seems similarly good.

giladbarkan-github commented 2 months ago

The bit search looks fine but why keep the binary search verison too?

I first thought it can help validate but what Andrew termed the "property" assertion seems similarly good.

Removed.