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

81–90 of 299 posts

Re: Computer scientists invent an efficient new way to count

#81

Post by cb321 »

xwolfi wrote: post #51
drycabinet wrote: post #45

Does finding the number of unique elements in a set actually require comparison of each element with everything else? Can't you use a hashtable? For every element, add it to the table (ignore if already exists), and finally, take a count of keys.

Imagine a million elements. How big must your hashtable be ? The article explains it very well, did you miss it ? It's a way to save memory. But to be honest I implemented it, ran it on Hamlet, and it's very wrong, it's barely useful but maybe if you just need a vague idea...

How big was your thresh? I found it pretty accurate: https://news.ycombinator.com/item?id=40388878

Re: Computer scientists invent an efficient new way to count

#82

Post by davidmurdoch »

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.

The authors of the article disagree with you.

Re: Computer scientists invent an efficient new way to count

#84

Post by aspenmayer »

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.

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

Re: Computer scientists invent an efficient new way to count

#85

Post by willvarfar »

pixelmonkey wrote: post #2

This algorithm seems to resemble HyperLogLog (and all its variants), which is also cited in the research paper. Using the same insight of the estimation value of tracking whether we've hit a "run" of heads or tails, but flipping the idea on its head (heh), it leads to the simpler algorithm described, which is about discarding memorized values on the basis of runs of heads/tails. This also works especially well (that…

Just curious, dusting off my distant school memories :)

How do the HLL and CVM that I hear about relate to reservoir sampling which I remember learning?

I once had a job at a hospital (back when 'whiz kids' were being hired by pretty much every business) where I used reservoir sampling to make small subsets of records that were stored on DAT tapes.

Re: Computer scientists invent an efficient new way to count

#87

Post by Sharlin »

usgroup wrote: post #68
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…

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…

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

Re: Computer scientists invent an efficient new way to count

#88

Post by chrisweekly »

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.

For someone who's pretty well-versed in English, but not a math-oriented computer scientist, this seems like a distinction without a difference. Please remedy my ignorance.

Re: Computer scientists invent an efficient new way to count

#89

Post by dchftcs »

usgroup wrote: post #68
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…

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

Re: Computer scientists invent an efficient new way to count

#90

Post by jameshart »

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.

They’re not very different things; the terms are used interchangeably in most contexts because in the real world all counting methods have some nonzero error rate.

We talk about ‘counting votes’ in elections, for example, yet when things are close we perform ‘recounts’ which we fully expect can produce slightly different numbers than the original count.

That means that vote counting is actually vote estimating, and recounting is just estimating with a tighter error bound.

I kind of think the mythology of the ‘countless stones’ (https://en.wikipedia.org/wiki/Countless_stones) is a sort of folk-reminder that you can never be too certain that you counted something right. Even something as big and solid and static as a standing stone.

The situations where counting is not estimating are limited to the mathematical, where you can assure yourself of exhaustively never missing any item or ever mistaking one thing’s identity for another’s.

Post reply on HN