23 ms·
We use Bloom filters to do something similar.
by akadien 15y ago
We use Bloom filters to do something similar.
- pork 15y agoYou should read the original Flajolet Martin paper if all you're doing is distinct count estimation.
- akadien 15y agoThanks. I've seen it before but will give a re-read.
- eternalban 15y agoDo you have a citation? A PDF link would be great and appreciated.
- minimax 15y agoLooks like Flajolet was responsible for both the linear probabilistic method and the hyper log log method. Probabilistic method (1985): http://algo.inria.fr/flajolet/Publications/FlMa85.pdf http://algo.inria.fr/flajolet/Publications/FlMa85.pdf Hyper log log (2007): http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf
- carterschonwald 15y agoMore than that, it's worth perusing all of Flajolet's papers, they're a wonderful intersection of analysis combinatorics and algorithms, and the recent book he had Coauthored (before his unfortunate passing last year) http://algo.inria.fr/flajolet/Publications/book.pdf http://algo.inria.fr/flajolet/Publications/book.pdf is an amazing book.