Show HN: An improved version of HyperLogLog

Re:Show HN: An improved version of HyperLogLog by buremba on Monday June 26, 2017 @06:17PM (#14640835)

Do you guys know any way to calculate the intersection of two HLL instances? The algorithm allows merging two sets but it's not that easy to take the intersection of them. A + B - (A U B) is not the optimal way so I would love to hear your suggestions.

[ Parent | on HN ]

Re:Show HN: An improved version of HyperLogLog by zintinio5 on Wednesday June 28, 2017 @03:31PM (#14657455)

Neustar Research has a good article on this which may be of interest to you. However, I think the approach they took was still based on the inclusion-exclusion principle (still a good read though).

* https://research.neustar.biz/2012/12/17/hll-intersections-2/

Another approach if you have the flexibility of changing your implementation, is to use a different type of data-sketch that is more amenable to set expressions. There is some discussion (and references) here:

* https://datasketches.github.io/docs/Theta/ThetaSketchFramewo...

* https://datasketches.github.io/docs/Tuple/TupleOverview.html

[ Parent | on HN ]

Re:Show HN: An improved version of HyperLogLog by seiflotfy on Monday June 26, 2017 @06:33PM (#14640967)

I have a way will post it soon

[ Parent | on HN ]

Re:Show HN: An improved version of HyperLogLog by buremba on Tuesday June 27, 2017 @03:42AM (#14643235)

Would love to hear about the solution, are you going to implement it or publish an article?

[ Parent | on HN ]