News for hackers. Stuff that matters.
Re:WyHLL: The most accurate 3-bits HyperLogLog by zwarag on Sunday March 14, 2021 @12:47PM (#26456717)
For anyone wondering what HyperLogLog is:

HyperLogLog is an algorithm for the count-distinct problem, approximating the number of distinct elements in a multiset. Calculating the exact cardinality of a multiset requires an amount of memory proportional to the cardinality, which is impractical for very large data sets. Probabilistic cardinality estimators, such as the HyperLogLog algorithm, use significantly less memory than this, at the cost of obtaining only an approximation of the cardinality. The HyperLogLog algorithm is able to estimate cardinalities of > 109 with a typical accuracy (standard error) of 2%, using 1.5 kB of memory.

Source: https://en.wikipedia.org/wiki/HyperLogLog

Re:WyHLL: The most accurate 3-bits HyperLogLog by wenc on Sunday March 14, 2021 @02:32PM (#26457567)
Hyperloglog is part of a class of algorithms known as “sketches”, which use precomputed probabilistic data structures to perform fast but approximate computations on very large data sets.

Supported computations include count distinct, frequency, sampling, and quantiles and histograms.

There’s a project called Apache Datasketches (developed at Yahoo) that implements production versions of these algorithms. They are useful in the implementations of search engines, discussion forum software, etc. that are designed for scale.

https://datasketches.apache.org/docs/Background/TheChallenge...

Another sketch is the well-known Bloom filter, which can quickly test if an element is part of a set without ever returning a false negative (useful for quickly checking a large database for whether a particular username is still available).

Re:WyHLL: The most accurate 3-bits HyperLogLog by skrebbel on Sunday March 14, 2021 @03:16PM (#26457978)
For anyone wondering what a multiset is:

A multiset is a set where each element can be present multiple times. In other words, it's like an array or list but you don't care about the order.

Re:WyHLL: The most accurate 3-bits HyperLogLog by vitus on Sunday March 14, 2021 @01:20PM (#26456948)
Aside: I'm admittedly grumpy about the commit history, which is filled with entries such as "Add files via upload" and "Update README.md".

That, together with the lack of documentation, makes it much more difficult to figure out what's special about this implementation.

Re:WyHLL: The most accurate 3-bits HyperLogLog by vitus on Sunday March 14, 2021 @01:45PM (#26457153)
https://github.com/redis/redis/blob/unstable/src/hyperloglog... seems to be the starting point, given a number of identical comments (complete with typos, e.g. "Estimate cardinality form register histogram"), function names, macros. Copyright isn't preserved, which is troubling in itself. There's a brief mention of Redis's HLL implementation in the README, which is a hint re: the code's origins.

The first divergence I see is in hllSparseToDense, although it seems more like a tweak to the input/output (passing in o->ptr instead of o, returning hdr instead of C_OK / C_ERR), than an algorithmic difference.

Line 550 contains a looser check:

    if (span == 0) return -1;
omitting the check that p >= end.

And... the only meaningful algorithmic change I found is in hllAdd, wherein we invalidate the cache if hllDenseAdd() returns 1.

There might be something else, but a lot of the details look to be standard (e.g. impl of murmurhash64a).

Re:WyHLL: The most accurate 3-bits HyperLogLog by vitus on Monday March 15, 2021 @05:49PM (#26469626)
Anyways, if anyone else wants to look at it: I've stripped the comments, clang-formatted both implementations, and uploaded the diff (sans newline differences) to pastebin.

https://pastebin.com/T520dzWV

It would be nice to have comments pointing out specifically what changes are important / why they were made.

Re:WyHLL: The most accurate 3-bits HyperLogLog by rurban on Monday March 15, 2021 @02:20AM (#26463074)
Yeah, WangYi only updates via some git gui. Same for his hash and prng. But those two set already the new standards, and the hll should be in the same league. Top of the class.
Re:WyHLL: The most accurate 3-bits HyperLogLog by yorwba on Sunday March 14, 2021 @12:49PM (#26456730)
Is there a companion paper somewhere explaining how it works? I tried to read the comments in the source but didn't really understand much. (Might be related to the fact that I never knew much about vanilla HyperLogLog to begin with.)
Re:WyHLL: The most accurate 3-bits HyperLogLog by Manozco on Sunday March 14, 2021 @02:24PM (#26457485)
This article by antirez helped me understand HyperLogLog a couple years ago http://antirez.com/news/75
Re:WyHLL: The most accurate 3-bits HyperLogLog by ithkuil on Sunday March 14, 2021 @07:11PM (#26460460)
Thank you for the article, nice read.

Just a small nitpick, for the craic:

> Moreover, while accessing the registers, we need to compute the sum of pow(2,-register) which involves floating point math. > [...] > * The floating point computation was modified in order to allow for multiple operations to be performed in parallel when possible. This was just a matter of adding parens. Floating point math is not commutative, but in this case there was no loss of precision.

Floating point addition is commutative. It is not associative though.

Re:WyHLL: The most accurate 3-bits HyperLogLog by rahimiali on Sunday March 14, 2021 @04:58PM (#26459098)
based on the comments it appears to rely on this paper: https://arxiv.org/abs/1702.01284
Re:WyHLL: The most accurate 3-bits HyperLogLog by jalk on Sunday March 14, 2021 @01:06PM (#26456846)
Re:WyHLL: The most accurate 3-bits HyperLogLog by pwnguin on Sunday March 14, 2021 @01:17PM (#26456931)
But what about the actual software question? What makes this different than redis hyper log log? Or statsite