3 ms·
You would think a HyperLogLog would be approximately good enough when follower counts reach tens of millions.
by lwansbrough 8y ago
You would think a HyperLogLog would be approximately good enough when follower counts reach tens of millions.
- fizx 8y agoHyperloglog was only just invented, and hadn't really made its way into the popular developer consciousness. Anyhow, the solution is easier than that (implement lock striping, i.e. https://stackoverflow.com/questions/16151606/need-simple-explanation-how-lock-striping-works-with-concurrenthashmap https://stackoverflow.com/questions/16151606/need-simple-exp...), but I was reorg'd away before my code hit production, so I'm not sure what happened there.
- lorenzhs 8y agoApproximate counters are much much older than HyperLogLog. Here’s something from 1978: https://www.inf.ed.ac.uk/teaching/courses/exc/reading/morris.pdf https://www.inf.ed.ac.uk/teaching/courses/exc/reading/morris.... Of course this solves a different problem because HyperLogLog is an, uh, interesting way to count followers (why would you need to do a count-distinct query? You can’t follow someone multiple times). In any case, the Flajolet Martin sketch dates back to 1985 and solves the same problem as HyperLogLog: https://en.wikipedia.org/wiki/Flajolet%E2%80%93Martin_algorithm https://en.wikipedia.org/wiki/Flajolet%E2%80%93Martin_algori...
- aflam 8y agoHere is nice presentation covering those: (link: https://www.cs.princeton.edu/~rs/talks/AC11-Cardinality.pdf https://www.cs.princeton.edu/~rs/talks/AC11-Cardinality.pdf)