Hacker News Reader

Comment by mjw1007 | Hacker News Reader

« Typo was as surprising inside as it was outside. Its similarity measure was based on trigram frequencies, which it counted in a 26x26x26 array. The small memory, which had barely room enough for 1-byte counters, spurred a scheme for squeezing large numbers into small counters. To avoid overflow, counters were updated probabilistically to maintain an estimate of the logarithm of the count. »

This sounds like something from the same family as hyperloglog

Wikipedia traces that back to the Flajolet–Martin algorithm in 1984. When would typo have been written?

View on HN

You are confusing the approximate counting of distinct elements (done by ingenious algorithms like hyperloglog or Flajolet–Martin) with the approximate counting of each element from a manageable set (done by incrementing the counters less and less often as they grow).

I believe that the paper backing the tool came out in the 70s, but if I ask IEEE for it it gives me back an awful PDF of one page that constrains a poor scan of the cover page of the paper and nothing else so I can’t confirm whether this idea was in it. Perhaps you might find more success: https://ieeexplore.ieee.org/abstract/document/6593963

Probably not related.

Sounds like it's just doing something like replacing `counter++` with `if(rand() % counter == 0) counter++`, so that the counter will increase slower and slower the larger it gets.

Absolutely related! This is essentially the same observation that makes Flajolet-Martin and HyperLogLog work - that when comparing counts, the exact low bits of large numbers "matter less" than the low bits of small numbers, so you can store the logarithm of the count. They differ in how they calculate the "incremental log" without storing the real values, based on what they are counting (high-dimensional events vs. high-cardinality sets).

https://link.springer.com/article/10.1007%2FBF01934993 which is one of Flajolet's early papers on the topic opens with "Approximate counting is an algorithm proposed by R. Morris". My guess would be Morris wrote it out of engineering need, and Flajolet and Martin followed up with formal analysis and resulting improvements.

Typo existed at least in Unix V5, with this source code: https://minnie.tuhs.org/cgi-bin/utree.pl?file=V5/usr/source/...

Unix V5 was released mid '70s, but as others have pointed out, counting is different from count distinct.

Seems to me like a variant of a counting Bloom filter.

Nope - counting bloom filters store an exact count of approximate events. This stores approximate counts of exact events.

If you count 5 "abc" and 5 "xyz" in a counting bloom filter, it will always say you had 10 events, but might say they were 10 of the same event.

If you count the same in Morris's structure, it will never confuse the two different sets, but might say one occurred 4 times and the other 8.

Of course, that means you can combine the two, for the benefits and downsides of both - storing very high (and inaccurate) counts of very sparse (and maybe misattributed) event sets.

Reply on news.ycombinator.com