-
A new count-distinct algorithm: “We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory.” Knuth likes it! “Their algorithm is not only interesting, it is extremely simple. Furthermore, it’s wonderfully suited to teaching students who are learning the basics of computer science. (Indeed, ever since I saw it, a few days ago, I’ve been unable to resist trying to explain the ideas to just about everybody I meet.) Therefore I’m pretty sure that something like this will eventually become a standard textbook topic.” — https://cs.stanford.edu/~knuth/papers/cvm-note.pdf (via mhoye)
(tags: algorithms approximation cardinality streaming estimation cs papers count-distinct distinct-elements)