rain 🌦️May 20, 2024

Got unreasonably excited about this new, incredibly straightforward count-distinct algorithm. The CVM algorithm is a direct replacement for HyperLogLog, it nerd-sniped Donald Knuth for weeks, *and* it can easily be taught in an entry-level CS course.

h/t @munin
https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/

Computer Scientists Invent an Efficient New Way to Count | Quanta Magazine

By making use of randomness, a team has created a simple algorithm for estimating large numbers of distinct objects in a stream of data.

Quanta Magazine
Show threadskategoat 🐐 🇵🇸May 21, 2024
@rain @munin what does X \ { a_i } mean? What is \ ?
Show threadrain 🌦️May 21, 2024
@felipe @munin hmm, where is that from?
Show threadskategoat 🐐 🇵🇸May 21, 2024
@rain @munin It's from the paper linked in the article, the second line in the loop* here:
Show threadrain 🌦️
@felipe @munin Ah thanks. \ is notation for set difference -- so in this case it just means "remove a_i from X"
May 21, 2024 at 1:02amWeb