4 ms·
Hyperloglog was only just invented, and hadn't really made its way into the popular developer consciousness. Anyhow, the solution is easier than that (implemen
by fizx 8y ago
Hyperloglog 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)