When I investigated quantile statistics a few years ago, I came to the conclusion that a histogram with log-linear bucketing is much simpler to implement than a T-digest, and more useful and easier to understand from an operational point of view. Log-linear bucketing corresponds to the kind of scientific notation x.yz * 10^e that is taught in high school, so 3 s.f. or a max 0.1% value error is reasonably straightforward and familiar. This kind of histogram can record outliers fairly cheaply, which is helpful because those are usually the most interesting values.
By contrast quantile sketches such as T-digest target a rank error (as opposed to a value error). The effect is that if you care about the 99.9% or 99.99% oddities, the sketches get big and waste space on the middle ranks, and you still lose information about the value of the outliers. It ends up not being competitive in terms of space or speed or precision compared to a histogram.
Probabilistic data structures feel magical when you work with them! The one I wish I had seen discussed/implemented here is a Cuckoo filter, which allows both deletion, and counting. Though the drawback is when the filter's capacity is nearly full, writing becomes significantly slower.
This post also provides a less dense technical overview of Bloom vs Cuckoo, and has previously been submitted here. 3 years ago, 8 years ago
IIRC, cuckoo filters also get you closer to the theoretical lower bound of log2(1/e) bits per item stored, whereas Bloom filters are at best 1.44 times that. So even though inserts slow down as you reach capacity, you could get back the performance by increasing capacity 10% or 20%, and you'd still be smaller than the equivalent Bloom filter.
Knowing only that this is a cardinality estimation that's really simple, I'm going to make a guess at what the algorithm could be.
If you pick n numbers each generated uniformly at random between 0 and 1, their minimum is 1/(n+1) in expectation, but with a bunch of variance. If you repeat this process k times and take the average, you should get something pretty close to 1/(n+1). So an algorithm could be:
Assume you have k independent hash functions h_0..h_k. Define p_i(x) to be h_i(x)/H where H is the largest possible hash. This normalizes hash outputs to be between 0.0 and 1.0. For each input x, we will compute p_0(x)..p_k(x).
For each i=0..k, track the minimum p_i(x) for all inputs x seen so far.
To get a cardinality estimate, let p be the average of the minimum p_is, and compute (1-p)/p (the inverse of 1/(n+1)).
EDIT: Nope, different. I was looking for something vaguely like hyper-log-log but simpler, while CVM impressively manages not to use hashes at all!
[For HyperLogLog,] Unsure uses the improved estimator by Otmar Ertl
Oh interesting, I haven't seen that approach yet! I'll have to read up on it.
I wonder how it compares to the Martingale transform for HyperLogLog. If you don't need the ability to merge HyperLogLog sketches, it's supposed to give a more accurate result than estimating directly from the counters:
Track the current cardinality = 0.0.
p is the probability that a newly-observed input will cause one of the HyperLogLog counters to change.
When a HyperLogLog counter changes, update cardinality += 1/p, then update p.
fanf | 2 hours ago
When I investigated quantile statistics a few years ago, I came to the conclusion that a histogram with log-linear bucketing is much simpler to implement than a T-digest, and more useful and easier to understand from an operational point of view. Log-linear bucketing corresponds to the kind of scientific notation x.yz * 10^e that is taught in high school, so 3 s.f. or a max 0.1% value error is reasonably straightforward and familiar. This kind of histogram can record outliers fairly cheaply, which is helpful because those are usually the most interesting values.
By contrast quantile sketches such as T-digest target a rank error (as opposed to a value error). The effect is that if you care about the 99.9% or 99.99% oddities, the sketches get big and waste space on the middle ranks, and you still lose information about the value of the outliers. It ends up not being competitive in terms of space or speed or precision compared to a histogram.
Doctor-X | 6 hours ago
These are so cool! I know Bloom filters, so thank you for introducing me to the others.
chai | an hour ago
Probabilistic data structures feel magical when you work with them! The one I wish I had seen discussed/implemented here is a Cuckoo filter, which allows both deletion, and counting. Though the drawback is when the filter's capacity is nearly full, writing becomes significantly slower.
This post also provides a less dense technical overview of Bloom vs Cuckoo, and has previously been submitted here. 3 years ago, 8 years ago
bitshift | 33 minutes ago
IIRC, cuckoo filters also get you closer to the theoretical lower bound of log2(1/e) bits per item stored, whereas Bloom filters are at best 1.44 times that. So even though inserts slow down as you reach capacity, you could get back the performance by increasing capacity 10% or 20%, and you'd still be smaller than the equivalent Bloom filter.
fanf | 2 hours ago
There’s a relatively new and simpler alternative to HyperLogLog for cardinality estimation that Knuth called the CVM algorithm (after its authors) https://buttondown.com/jaffray/archive/the-cvm-algorithm/
justinpombrio | an hour ago
Knowing only that this is a cardinality estimation that's really simple, I'm going to make a guess at what the algorithm could be.
If you pick
nnumbers each generated uniformly at random between 0 and 1, their minimum is1/(n+1)in expectation, but with a bunch of variance. If you repeat this processktimes and take the average, you should get something pretty close to1/(n+1). So an algorithm could be:kindependent hash functionsh_0..h_k. Definep_i(x)to beh_i(x)/HwhereHis the largest possible hash. This normalizes hash outputs to be between 0.0 and 1.0. For each inputx, we will computep_0(x)..p_k(x).i=0..k, track the minimump_i(x)for all inputsxseen so far.pbe the average of the minimump_is, and compute(1-p)/p(the inverse of1/(n+1)).EDIT: Nope, different. I was looking for something vaguely like hyper-log-log but simpler, while CVM impressively manages not to use hashes at all!
fanf | 46 minutes ago
Oh, another classic (1970s) randomized algorithm is Robert Morris’s “Counting Large Numbers of Events in Small Registers” abstract pdf
bitshift | 2 hours ago
Oh interesting, I haven't seen that approach yet! I'll have to read up on it.
I wonder how it compares to the Martingale transform for HyperLogLog. If you don't need the ability to merge HyperLogLog sketches, it's supposed to give a more accurate result than estimating directly from the counters:
cardinality = 0.0.pis the probability that a newly-observed input will cause one of the HyperLogLog counters to change.cardinality += 1/p, then updatep.