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.

It all started with that dinner with Don (Knuth). As part of the workshop at Simons Institute on Satisfiability [where I was fortunate to be invited as a co-organizer], we had invited Don and to our delight, not only he accepted the invite but also decided to stay for the entire week. Simons institute staff suggested that we take Don out for dinner and I had the privilege of sitting next to him at dinner, and we talked about many things. The next morning I walked to Don and mentioned that I would love to introduce him to our algorithm for distinct elements estimation.

We went for lunch at the faculty club and 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.