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

21–30 of 299 posts

Re: Computer scientists invent an efficient new way to count

#21

Post by card_zero »

imoverclocked wrote: post #3

When do we stop calling this counting and start calling it estimation?

Seems this is one of those things like UUIDs where we rely on it being very unlikely to be wrong, because statistics.

> the accuracy of this technique scales with the size of the memory.

I wonder if that's proportional to the number of distinct items to count, though.

> if the [memory] is so big that it fits all the words, then we can get 100% accuracy

Yes, but then the algorithm isn't being used any more, that's just normal counting.

They counted the distinct words in Hamlet with a memory size of 100 words, about 2.5% of the number to find, and got a result that was off by 2. If you do the same with the whole of Shakespeare, again using 2.5% of the memory needed to hold all the distinct words, is the accuracy better?

Anyway, this is limited to counting, and doesn't help list what the words are, though quickly counting them first is perhaps a way to speed up the task of actually finding them?

Re: Computer scientists invent an efficient new way to count

#22

Post by usgroup »

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.

Re: Computer scientists invent an efficient new way to count

#26

Post by hmottestad »

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…

It’s also possible to use HLL to estimate the cardinality of joins since it’s possible to estimate both the union and the intersection of two HLLs.

http://oertl.github.io/hyperloglog-sketch-estimation-paper/

Re: Computer scientists invent an efficient new way to count

#27

Post by [deleted] »

card_zero wrote: post #21
imoverclocked wrote: post #3

When do we stop calling this counting and start calling it estimation?

Seems this is one of those things like UUIDs where we rely on it being very unlikely to be wrong, because statistics. > the accuracy of this technique scales with the size of the memory. I wonder if that's proportional to the number of distinct items to count, though. > if the [memory] is so big that it fits all the words, then we can get 100% accuracy Yes, but then the algorithm isn't being used any more, that's jus…

[deleted]

Re: Computer scientists invent an efficient new way to count

#28

Post by devnonymous »

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 ?

Re: Computer scientists invent an efficient new way to count

#29

Post by thesz »

HyperLogLog uses additions, it keeps sums. Thus, you can subtract one HLL sums from other. This is useful if stream supports deletion. Streams with deletions can be found in log-structured merge trees, for one example, so one can estimate count of distinct elements in all of the LSM tree hierarchy.

The algorithm in the paper does not allow for deletions.

Also, if one counts statistics of the stream of large elements (say, SHA-512 hashes, 64 bytes per hash), this algorithm requires some storage for elements from this stream, so memory requirement is O(table size * element size).

Re: Computer scientists invent an efficient new way to count

#30

Post by vanderZwan »

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

Post reply on HN