A cursory glance suggests that it's O(N) in size of you want guarantees against an adversary. The bucket collapsing method reduces accuracy in collapsed buckets. If so, the attack would be easiest when distributed to manipulate data splits so that you collapse significant blocks of data together when merging.
I'll see if I have a chance to read things more carefully this coming week. jon On Sat, Oct 19, 2019, 10:32 AM leerho <[email protected]> wrote: > Science team, > > Would you please take a look at this sketch. It appears to address the > "relative error" for quantiles issue we have been discussing recently. > > https://blog.acolyer.org/2019/09/06/ddsketch/ > > Thanks, > > Lee. >
