If you refer to the subtitle of the paper - An Algorithm for the (Text) Book - I think that is actually a reference to something *Paul Erdos allegedly said about some proofs are so elegant in their simplicity and beauty that they are "from The Book", like representing some divine Platonic ideal.

Given that Knuth himself reviewed it, he might have remarked that this was one of those algorithms! Perhaps the authors decided to include it in the title as a not-so-humble brag (which would be well-earned if that's the case!)

edit: originally this comment said Knuth was the one who said this about some algorithms being from The Book, but that was my faulty memory.

From the abstract: "... All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. 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 ...."

This is really twisting it, I don't find pairwise indepedence to be more advanced than applying a Chernoff bound. In this problem it'd mostly be the difference of using a Cherbyshev type bound or Chernoff bound.

Pairwise independence is to give the algorithm stronger guarantees and let it work with a simple hash function like ax+b, otherwise probably most existing algorithms can be simplified in the same way. The most similar algorithm is BJKST, which is almost identical except for specifyimg the sampling mechanism to require less randomness.

To someone who worked on this type of thing before, it's like seeing people familar with LLMs say "oh yet another X-billion parameter model on github doing more or less the same".

The Chernoff bound needed in this work can be derived from Binomial distribution (with Stirling's approximation);

I have worked on pairwise independent hash functions for a decade and every time I introduce such a function, it feels like magic. The notion of pairwise independence is easy to explain but the notion of pairwise independent hash functions isn't.

The other strength of our work is that it can work for general settings of sets for which pairwise independent hash functions are not known. Please see: https://dl.acm.org/doi/10.1145/3452021.3458333

The point is that the subtitle's is pretty clearly intended to have a dual meaning, it wouldn't be phrased like that otherwise.

I thought The Book was an Erdos thing. I wonder who used it first.

"During a lecture in 1985, Erdős said, `You don't have to believe in God, but you should believe in The Book.`"

https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK

I think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.

I liked this part. They got Knuth to review it, and found mistakes. That's kind of cool, in its own way.

    We are deeply grateful to Donald E. Knuth for his thorough review, 
    which not only enhanced the quality of this paper (including fixing
    several errors) but has also inspired us for higher standards.

>The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks.

Doesn't seem like it. Seems like an algorithm (similar to other approximate cardinality estimation algorithms) with huge applicability.

From the abstract: "All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. 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."

That just says that this is also simpler and more accessible algorithm, suitable even for undegraduate textbooks.

Not that this is just useful for textbooks, a mere academic toy example, which would be something else entirely.

This is both accessible AND efficient.

> "The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks."

If you're saying it's just for "undergraduates and textbooks", as opposed to just being simple enough for them to use but not limited to them, would you mind explaining what makes it useful for undergrads but not for professionals?

From the abstract: "All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. 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."

That still only speaks to it being simple enough for students, not whether its too simple for any other use vs. useful enough that students who learn it will spend the rest of their lives using it.

For example word processor software is commonly described as simple enough for children to use at school, that doesn't mean that word processor software is of no use to adults.

the reason it's too simple for most real world use is that hyper-log-log is the "good" version of this technique (but is harder to prove that it works)

Simplicity in an algorithm has limited direct impact on its usefulness in industry where libraries are prevalent.

Consider mapping structures with Θ(k) expected lookup times. The simplest implementation is a hash table with chaining. Open-addressing is a bit more complicated, but also more common. Tries, which have O(k) worst-case lookup times are often covered in Undergraduate courses and are definitely easier to analyze and implement than forms of open-addressed hash-tables that have O(k) guarantees (e.g. Cuckoo hashing).

My interpretation from the paper is that this algorithm is simpler than other options but also worse. So in a professional context you'd use one of those instead

The blog post was more than half padding. Good that the algorithm is so simple it's hard to write a full length blog post about it!

And yet the blog post still got it wrong:

> Now you move forward with what the team calls Round 1. Keep going through Hamlet, adding new words as you go. If you come to a word that’s already on your list, flip a coin again. If it’s tails, delete the word; heads, and the word stays on the list. Proceed in this fashion until you have 100 words on the whiteboard. Then randomly delete about half again, based on the outcome of 100 coin tosses. That concludes Round 1.

It's not just removals you test with N coin flips in Round N, it's whether to insert the new item at all.

Yeah, I noticed the same thing. Quanta's version of the algorithm is not only confusing, it's also wrong.

I think the pseudocode in the paper is very hard to beat.

I originally used Guttenburgh to get Hamlet and coded the Quanta method in Python and it did not work. I then moved to Algorithm 1 in the paper and got Copilot to (mis) convert it to Python and then spent time getting Copilot to admit its mistakes. The resultant code seemed to work but I found the Quanta suggested data of the words of hamlet to be uninspiring as for the calculated theta (max set size before halving), was often from ~50% of the total number of words in hamlet to often more than the words in hamlet. I've yet to investigate theta in more depth...

Link to abstract: https://arxiv.org/abs/2301.10191

I agree the paper is better than the blog post, although one criticism I have of the CVM paper is that it has some termination/algo exit condition instead of what Knuth's CVM notes (refed else-thread here) do which is just a loop to ensure getting more space in the reservoir halving-step. It seems more work to explain the https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1]

[1] https://news.ycombinator.com/item?id=40388878

On that note, I'm also unfamiliar with this \ operator notation which is used without explanation.

    X ← X \ {ai}

That is conventional set subtraction notation. "Assign to X the same set minus all elements of the set {a_i}".

One example source, but it is pretty common in general: http://www.mathwords.com/s/set_subtraction.htm

Set difference.

Set X becomes X without element ai. This is the case whether ai was in the set X before the step was taken.

I've known that symbol for decades, never knew it's name - up-tack it is. Ta!

You are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being correct).

It wasn't easy to see that loop would have added benefit -- that's where Knuth's ingenuity comes in.

It's been a while, and maybe my brain has smoothened since my time in CS, but man this looks more confusing than it needs to be.

First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.

Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not. Looking at it a bit more, it seems like no you don't. You pick a threshold, and then depending on the size of the stream the probability changes. But the algorithm is described as if it had a single output, which is not the case(?).

And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.

Anyway, here's my take in Golang: https://github.com/betamos/distinct

I factored out the threshold parts into a helper instead, which makes a lot more sense than accidentally allocating too much memory.

Perhaps there should be a method for estimating the confidence/error rate. Nobody knows the size of a stream upfront, so it would make more sense to update these values as you go. Brain is not strong enough to implement it, but feel free to send a PR.

[I am one of the authors].

We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf

But yes, our theorems can be reworked to estimate the confidence/error rate; that's what Knuth did: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf

Didn’t realize you were here so let me be clear that I did overall find the paper so approachable that I could implement it with only a couple of outside pointers (also a little clever impl optimization around storing p if you’re curious). The above should be read more as “even this well-written simplified paper is not necessarily trivial to understand for practicians”. So more of a general point around academic obscurity.

> But yes, our theorems can be reworked to estimate the confidence/error rate

I think that’s useful for practical implications. Also, for practical use, how does one decide the tradeoff between delta and epsilon? Perhaps it’s covered elsewhere, but I have a hard time intuiting their relationship.

I fully agree with you and this is indeed one of my criticisms of modern academic writing -- we tend to write papers that are just very hard for anyone to read.

So delta refers to the confidence, i.e., how often are you willing to be wrong, and epsilon is tolerance with respect to the actual count.

We have found that in general, setting delta=0.1 and espilon=0.8 works fine for most practical applications.

> First, the contradiction thing. It's just.. An error/panic, why? Anyway, fine.

I suspect due to the details of the proof. This condition looks likely to me for very small set cardinality making the algorithm inappropriate for all-weather. See page 3 of the paper where Algorithm 2 is introduced. They show that in the failure condition, the likelihood of the algorithm returning a value outside of the epsilon bounds is higher.

> Then, there's the whole premise of 1..m: I'm still not sure if the size needs to be known upfront or not.

m sizes the threshold, if it is too small, the error bounds guaranteed by the algorithm will be larger than expected, and vice versa if m is too large.

> And btw, I didn't know about the Chernoff bounds and delta/epsilon are not explained at all in the paper, which added to the confusion a lot.

Papers typically do not spend words on basics and those are standard concepts.

> Perhaps there should be a method for estimating the confidence/error rate.

You can't resize the stream easily because p implicitly depends on m via the thresh cardinality condition and if you were to change m then your p updates would not correspond. As a result you may not be able to rely on the error bounds. Note though that stream doesn't mean infinite or very large: take it to mean one item at a time. The point of this algorithm is to bound space complexity to something small. Have a look at thresh and note that log2(1e50) is just 166: if you did have a very large stream of indeterminate length you could also just pick a very large m.