Druid: Configurable HyperLogLog accuracy

[DaimonPl]

Even though current algorithm claims to be "98% right" we've found that error is sometimes even around 4-5%

Idea is to have ability to increase accuracy (at the cost of speed and space) for such cases.

I assume that for proper estimation entire datasource would need to be aggregated with same accuracy setting

Is number of buckets proper candidate for accuracy prameter?

[DaimonPl]

@gianm maybe you have some ideas about this one? :)

[DaimonPl]

@leventov @fjy maybe you? :)

[gianm]

@DaimonPl some thoughts:

• The "98% right" thing is meant to refer to average error of HyperLogLog, but certainly the error in any particular case can be greater than that.
• Druid's implementation deviates from the standard algorithm (see http://druid.io/blog/2014/02/18/hyperloglog-optimizations-for-real-world-systems.html) in a way that decreases storage space but can increase the error slightly in some cases.
• Yes changing the number of buckets is a good way to improve the accuracy. In addition you could undo the storage space optimization.
• But watch out since both of the above changes would affect the storage format, meaning you may be incompatible with already-written hyperUnique columns.

[elverkilde]

We are also observing large errors (7-8%) especially on smaller cardinalities (<40000). This is pretty much in line with the bias observed in the Google paper.

Did you consider any of the improvements mentioned in the Google paper (HyperLogLog++)?

[stale[bot]]

This issue has been marked as stale due to 280 days of inactivity. It will be closed in 2 weeks if no further activity occurs. If this issue is still relevant, please simply write any comment. Even if closed, you can still revive the issue at any time or discuss it on the [email protected] list. Thank you for your contributions.

[stale[bot]]

This issue has been closed due to lack of activity. If you think that is incorrect, or the issue requires additional review, you can revive the issue at any time.

[leventov]

Related: #7160