At today's Stanford theory seminar, Don Knuth talked about our algorithm for distinct elements estimation in a stream.

Don also shared a note about the algorithm, which you can find here.

That dinner with Don (Knuth) changed everything. I introduced Don to our algorithm for distinct elements, and he fell in love with it. Quoting him, "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."

But of course, Don, being Don, didn't just write about the algorithm; his extension of our algorithm also provides unbiased estimation. So it would be appropriate to call it Algorithm KCVM, not CVM. Discussing with Don (in-person and over emails) has been one of my most inspiring and intense experiences: his curiosity, focus, precision, and generosity are unmatched.

And, of course, the program in CWeb can be found here.