Implement CpcSketch

[tisonkun]

https://datasketches.apache.org/docs/CPC/CpcSketches.html

I noticed my current sketch for estimating unique values is more like the CpcSketch than an HllSketch #3 (comment)

So I track this issue for the task and discuss the difference between Hll and Cpc. @leerho is one always better than the other? Or we can use either to get similar results.

Upon the implementation part, the last time I found so many flavors and I don't quite understand what PairTable is for. I'd appreciate it if one can share the design ideas and where to start :P

[notfilippo]

https://datasketches.apache.org/docs/DistinctCountMeritComparisons.html I found this very useful.

[leerho]

The CPC sketch is a different animal from HLL. There is quite a bit of material on the DataSketches Web site about CPC and how it compares to HLL and Theta at a high level. It is also a pretty sophisticated sketch and implementing it needs to be done with care. The CPC concept and implementation was conceived by our late colleague Kevin Lang alone, and was a huge undertaking. He spent nearly 2 years in the research, design, development and publication of his work on it. Our CPC sketch is also received recognition in the theoretical literature and has also inspired follow-on theoretical work that have extended its performance even more. See ExaLogLog by Otmar Ertl.

[leerho]

To Understand CPC:

• First thoroughly understand HLL and how and why it works.
• Then I would recommend we have a 1:1 video conf & I could go over it with you. But sometime in January.