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

91–100 of 299 posts

Re: Computer scientists invent an efficient new way to count

#91

Post by cb321 »

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.

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

Re: Computer scientists invent an efficient new way to count

#92

Post by lupire »

112233 wrote: post #11
vlovich123 wrote: post #6

Earlier quoted context omitted.

As soon as people start reading past the headline.

tbh, the title (and introduction) did a lot to dissuade me from finishing the (really good) article. It was actually informative, why dress it as a SEO blogspam?

It's Quanta. Their mission is to make laypeople like math (not understand math), so they drown the math in sugar.

Re: Computer scientists invent an efficient new way to count

#93

Post by datavirtue »

Anduia wrote: post #56
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.

Using a hashtable is effective because you only compare elements within their hash buckets, not the entire set. However, they can become inefficient with very large datasets due to memory usage and processing time, which is where approximate counts shine.

This algorithm is still spinning a lot of random. I would guess that this is much less overhead than hashing but still seems like it could be significant.

Re: Computer scientists invent an efficient new way to count

#94

Post by lupire »

jameshart wrote: post #90
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 r…

Come on. There is a fundamental difference between trying to get an exactly answer and not trying to get an exactly correct answer.

Re: Computer scientists invent an efficient new way to count

#95

Post by bzuker »

wmwragg wrote: post #12
akamoonknight wrote: post #9

I don't know a word or phrase for this, but I really enjoy any examples of "thinking outside the box" like this because it's something I struggle with in my professional career. Learning not only the right ways to solve problems, but figuring out the questions to ask that make solving the problems you have easier or even in some cases possible. In this case, it's hey, we don't need exact numbers if we can define a pr…

I think it's generally thought of as "lateral thinking", Edward de Bono has written a few books about it you might find interesting.

any particular one you'd recommend?

Re: Computer scientists invent an efficient new way to count

#97

Post by lupire »

chrisweekly wrote: post #88
dools wrote: post #33

Earlier quoted context omitted.

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.

My GP was wrong, but the words are different.

Eatimation is a procedure the generates an estimate, which is a kind of approximation, while approximation is a result value. They are different "types", as a computer scientist would say. An approximation is any value that is justifiably considered to be nearly exact. ("prox" means "near". See also "proximate" and "proxy".)

Estimation is one way to generate an approximation. An estimate is a subtype of an approximation. There are non-estimation ways to generate an approximation. For example, take an exact value and round it to the nearest multiple of 100. That generates an approximation, but does not use estimation.

Re: Computer scientists invent an efficient new way to count

#98

Post by [deleted] »

swores wrote: post #71
usgroup wrote: post #69

Earlier quoted context omitted.

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.

[deleted]

Re: Computer scientists invent an efficient new way to count

#99

Post by jameshart »

lupire wrote: post #94
jameshart wrote: post #90

Earlier quoted context omitted.

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

Come on. There is a fundamental difference between trying to get an exactly answer and not trying to get an exactly correct answer.

It’s not a fundamental difference, it’s a fundamental constraint.

There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway.

We still call procedures for counting things under those circumstances ‘counting’.

The constraints on this problem (insufficient memory to remember all the unique items you encounter) are one such situation where even computerized counting isn’t going to be exact.

Re: Computer scientists invent an efficient new way to count

#100

Post by coldtea »

usgroup wrote: post #70
coldtea wrote: post #40

Earlier quoted context omitted.

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

Post reply on HN