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/
@felipe @rain @munin It felt impossible not to just give this a quick try, so I implemented it in an @observablehq notebook.
This notebook implements the an approximate algorithm for counting the number of distinct items in a stream of data. For large streams of data which may not even fit in memory, this is a classic computer science problem. The algorithm implemented here comes from the paper Distinct Elements in Streams: An Algorithm for the (Text) Book by Chakraborty, Vinodchandran, and Meel, all of which is nicely summarized in Quanta Magazine's article, Computer Scientists Invent an Efficient New Way to Count. It's so simpl
@rreusser @felipe @rain @observablehq
lol, amazing, it forms a normal curve around the 'right' value, just like you'd intuitively expect
rain 🌦️
skategoat 🐐 🇵🇸
Ricky Reusser
Fi 🏳️⚧️