Computer scientists invent an efficient new way to count
quantamagazine.org
Computer scientists invent an efficient new way to count
1–10 of 299 posts
Re: Computer scientists invent an efficient new way to count
#2This 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 is, efficiently) in the streaming case, allowing you to keep something resembling a "counter" for the distinct elements, albeit with a error rate.
The benefit of HyperLogLog is that it behaves similarly to a hash set in some respects -- you can add items, count distinct them, and, importantly, merge two HLLs together (union), all the while keeping memory fixed to mere kilobytes even for billion-item sets. In distributed data stores, this is the trick behind Elasticsearch/OpenSearch cardinality agg, as well as behind Redis/Redict with its PFADD/PFMERGE/PFCOUNT.
I am not exactly sure how this CVM algorithm compares to HLL, but they got Knuth to review it, and they claim an undergrad can implement it easily, so it must be pretty good!
Re: Computer scientists invent an efficient new way to count
#3When do we stop calling this counting and start calling it estimation?
Re: Computer scientists invent an efficient new way to count
#4CS guys always wanting to throw away a good system and start from scratch.
Re: Computer scientists invent an efficient new way to count
#5When do we stop calling this counting and start calling it estimation?
Yes, even the subtile states "a simple algorithm for estimating large numbers of distinct objects".
Re: Computer scientists invent an efficient new way to count
#6When do we stop calling this counting and start calling it estimation?
As soon as people start reading past the headline.
Re: Computer scientists invent an efficient new way to count
#7> The trick, he said, is to rely on randomization.
> When the space is full, press pause and flip a coin for each word. Heads, and the word stays on the list; tails, and you delete it.
I wasn't expecting to go that far: randomization. How can you verify if the answer is good? Only approximation, maybe..
Re: Computer scientists invent an efficient new way to count
#8CS guys always wanting to throw away a good system and start from scratch.
Which good system are we talking about ?
Re: Computer scientists invent an efficient new way to count
#9I 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 probabilistic range given defined parameters. Other problems are gonna have other questions. I guess my hope is that if I see enough examples I'll be able to eventually internalize the thought process and apply it correctly.
Re: Computer scientists invent an efficient new way to count
#10CS guys always wanting to throw away a good system and start from scratch.
Which good system are you referring to?