Alternative HyperLogLog implementation with higher accuracy

[Jackie-Jiang]

Current HyperLogLog implementation is fairly old: https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java

There are several alternative implementations that can potentially reduce memory cost and improve accuracy.
https://github.com/axiomhq/hyperloglog
https://github.com/clarkduvall/hyperloglog

[xiangfu0]

@jamesyfshao just fyi, I think mobile analytics is using fasthll right now

[Jackie-Jiang]

@jamesyfshao If you are using FASTHLL, please check out the documentation change in #4251 as we are moving away from FASTHLL to DISCTINCTCOUNTHLL.

[xiangfu0]

Could you elaborate more on the performance and do you do the performance testing?

Below is how Uber uses fasthll:
For fasthll, there is a pre-aggregation phase before data ingestion, e.g. we have a job publish all the dimension combinations and it's corresponding unique counting FASTHLL object every 5mins and offline job is daily basis. This leads to data volume reduction to only 10% of the original size.

From both storage and computation perspective, fasthll is more efficient IMO.

[Jackie-Jiang]

@fx19880617 FASTHLL takes String type of serialized HyperLogLog objects, while DISTINCTCOUNTHLL can take BYTES (byte array) type of serialized HyperLogLog objects, which is more efficient in both storage and deserialization. The BYTES support for DISTINCTCOUNTHLL is new added after Pinot supporting BYTES data type.

[xiangfu0]

Got it. @jamesyfshao ^^

[xiangfu0]

also cc @icefury71 ^^

[extesy]

https://github.com/prasanthj/hyperloglog is a java version (already in maven) which can be easily integrated.

[extesy]

@Jackie-Jiang @fx19880617 Any follow-up?

[extesy]

@Jackie-Jiang @fx19880617 @jamesyfshao any follow-up?

[Jackie-Jiang]

After some research, will try out the DataSketches (https://datasketches.github.io) library and evaluate its performance.

[leerho]

@Jackie-Jiang
We haven't evaluated all of the above HLL variants, but we have a detailed comparison of the DataSketches HllSketch vs the Clearspring HLL++ implementation on our website:

https://datasketches.github.io/docs/HLL/Hll_vs_Hllpp.html

There is also a detailed discussion about measuring sketch performance in general that might be helpful.

Note that the above links are to our old website, which has not yet migrated to Apache yet. The links will soon change to datasketches.apache.org.

[deemoliu]

Hi @Jackie-Jiang

currently pinot is using https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLog.java

we have some customers observed that HLL++ has higher accuracy than HLL when cardinality of dimension is at 10k-100k.

We also tried different log2m values for distinctCountHLL but it will bring more load on CPU.

is there a plan to support hll++ in Pinot distinctHLLL (or other functions)? https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/cardinality/HyperLogLogPlus.java

[deemoliu]

linked a Draft PR: #11346