Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Computer scientists invent an efficient new way to count

quantamagazine.org

Post reply on HN
Print view View original

31–40 of 299 posts

Re: Computer scientists invent an efficient new way to count

#31

Post by 112233 »

devnonymous wrote: post #28
112233 wrote: post #13

After skimming Knuth's paper — does the algorithm work if values are hashed, that is, the "uniform deviate" is selected deterministically for each unique value of the stream?

Not sure which Knuth paper you're referring to but skimming through the article my understanding is this algorithm works /only/ if the values are hashable. IOW how else does one define unique/distinct values ?

https://cs.stanford.edu/~knuth/papers/cvm-note.pdf

note how "u"s are selected every time value is not in a list. I don't read it as being a hash.

Re: Computer scientists invent an efficient new way to count

#32

Post by hcs »

devnonymous wrote: post #28
112233 wrote: post #13

After skimming Knuth's paper — does the algorithm work if values are hashed, that is, the "uniform deviate" is selected deterministically for each unique value of the stream?

Not sure which Knuth paper you're referring to but skimming through the article my understanding is this algorithm works /only/ if the values are hashable. IOW how else does one define unique/distinct values ?

https://cs.stanford.edu/~knuth/papers/cvm-note.pdf

Looks like it was posted at the time https://news.ycombinator.com/item?id=36079213 but not much discussed. I found it over here https://news.ycombinator.com/item?id=40387594

Re: Computer scientists invent an efficient new way to count

#34

Post by ranguna »

dools wrote: post #33
melq wrote: post #24

Estimating the amount of unique elements in a set and counting the amount of unique elements in a set are very different things. Cool method, bad headline.

It's an approximation, not an estimation.

Still very different things, no?

Re: Computer scientists invent an efficient new way to count

#35

Post by hcs »

112233 wrote: post #31
devnonymous wrote: post #28

Earlier quoted context omitted.

Not sure which Knuth paper you're referring to but skimming through the article my understanding is this algorithm works /only/ if the values are hashable. IOW how else does one define unique/distinct values ?

https://cs.stanford.edu/~knuth/papers/cvm-note.pdf note how "u"s are selected every time value is not in a list. I don't read it as being a hash.

I think the analysis relies on independent random "u"s, even for the same key.

Re: Computer scientists invent an efficient new way to count

#36

Post by kibibu »

vanderZwan wrote: post #30
usgroup wrote: post #22

I found the paper took about as long to read as the blog post and is more informative: 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.

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 dec…

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

Re: Computer scientists invent an efficient new way to count

#39

Post by stevesimmons »

kibibu wrote: post #36
vanderZwan wrote: post #30

Earlier quoted context omitted.

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 dec…

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

Re: Computer scientists invent an efficient new way to count

#40

Post by coldtea »

usgroup wrote: post #22

I found the paper took about as long to read as the blog post and is more informative: 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.

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

Post reply on HN