6 ms·

I found the paper took about as long to read as the blog post and is more informative: https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191 It is

I found the paper took about as long to read as the blog post and is more informative: https://arxiv.org/pdf/2301.10191 https://arxiv.org/pdf/2301.10191 It is about estimating the cardinality of a set of elements derived from a stream. The algorithm is so simple, you can code it and play with it whilst you read the paper. The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks.

vanderZwan 2y ago
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.
- kibibu 2y ago
  I thought The Book was an Erdos thing. I wonder who used it first.
  - stevesimmons 2y ago
    "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 https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
  - vanderZwan 2y ago
    I think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.
- usgroup 2y ago
  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 ...."
  - Sharlin 2y ago
    The point is that the subtitle's is pretty clearly intended to have a dual meaning, it wouldn't be phrased like that otherwise.
  - dchftcs 2y ago
    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".
    - kuldeepmeel 2y ago
      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 https://dl.acm.org/doi/10.1145/3452021.3458333
- cschmidt 2y ago
  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.
coldtea 2y ago
>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.
- usgroup 2y ago
  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."
  - coldtea 2y ago
    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.
swores 2y ago
> "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?
- pfsalter 2y ago
  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
- usgroup 2y ago
  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."
  - swores 2y ago
    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.
    - deleted 2y ago
      [deleted]
    - adgjlsfhk1 2y ago
      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)
resonious 2y ago
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!
- mpalmer 2y ago
  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.
  - Paddy3118 2y ago
    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...
  - gwillen 2y ago
    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.
aspenmayer 2y ago
Link to abstract: https://arxiv.org/abs/2301.10191 https://arxiv.org/abs/2301.10191
cb321 2y ago
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 https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1] [1] https://news.ycombinator.com/item?id=40388878 https://news.ycombinator.com/item?id=40388878
- imglorp 2y ago
  On that note, I'm also unfamiliar with this \ operator notation which is used without explanation. X ← X \ {ai}
  - jtanderson 2y ago
    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 http://www.mathwords.com/s/set_subtraction.htm
  - rocqua 2y ago
    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.
- _a_a_a_ 2y ago
  I've known that symbol for decades, never knew it's name - up-tack it is. Ta!
- kuldeepmeel 2y ago
  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.
klabb3 2y ago
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 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.
- kuldeepmeel 2y ago
  [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 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 https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
  - klabb3 2y ago
    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.

vanderZwan 2y ago

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.

kibibu 2y ago
I thought The Book was an Erdos thing. I wonder who used it first.
- stevesimmons 2y ago
  "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 https://en.wikipedia.org/wiki/Proofs_from_THE_BOOK
- vanderZwan 2y ago
  I think you're right, I must have confused the two. I'll edit my comment to reduce the spread of misinformation.
usgroup 2y ago
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 ...."
- Sharlin 2y ago
  The point is that the subtitle's is pretty clearly intended to have a dual meaning, it wouldn't be phrased like that otherwise.
- dchftcs 2y ago
  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".
  - kuldeepmeel 2y ago
    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 https://dl.acm.org/doi/10.1145/3452021.3458333
cschmidt 2y ago
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.

coldtea 2y ago

>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.

usgroup 2y ago
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."
- coldtea 2y ago
  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.

swores 2y ago

> "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?

pfsalter 2y ago
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
usgroup 2y ago
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."
- swores 2y ago
  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.
  - deleted 2y ago
    [deleted]
  - adgjlsfhk1 2y ago
    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)

resonious 2y ago

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!

mpalmer 2y ago
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.
- Paddy3118 2y ago
  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...
- gwillen 2y ago
  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.

aspenmayer 2y ago

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

cb321 2y ago

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 https://en.wikipedia.org/wiki/Up_tack than just do the loop. [1] [1] https://news.ycombinator.com/item?id=40388878 https://news.ycombinator.com/item?id=40388878

imglorp 2y ago
On that note, I'm also unfamiliar with this \ operator notation which is used without explanation. X ← X \ {ai}
- jtanderson 2y ago
  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 http://www.mathwords.com/s/set_subtraction.htm
- rocqua 2y ago
  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.
_a_a_a_ 2y ago
I've known that symbol for decades, never knew it's name - up-tack it is. Ta!
kuldeepmeel 2y ago
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.

klabb3 2y ago

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 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.

kuldeepmeel 2y ago
[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 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 https://cs.stanford.edu/~knuth/papers/cvm-note.pdf
- klabb3 2y ago
  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.