Cardinality Estimation (2011) [pdf]

https://www.cs.princeton.edu/~rs/talks/AC11-Cardinality.pdf

by ingve • 10 years ago

134 11 10 years ago

cs.princeton.edu

As a layperson, I found this to be a pretty accessible background that ultimately leads up to a useful description of HyperLogLog. I had never heard of Philippe Flajolet before, and now I'm glad I have.

mrcactu5• 10 years ago

Understood since Babbage: AofA is a scientific endeavor.

• Start with a working program (algorithm implementation).

• Develop mathematical model of its behavior.

• Use the model to formulate hypotheses on resource usage.

• Use the program to validate hypotheses.

• Iterate on basis of insights gained.

Knuth's methodology (slide 2) can be used to analyze programs we currently use, which have no obvious mathematical content.

e.g. how do these fine code linters spot errors in your code? https://github.com/showcases/clean-code-linters but also does it manage your keystroke events an present information to you in a handy interface? algorithms are managing all of that

tmsh• 10 years ago

Sedgewick also has a nice coursera lecture on 2-3 trees leading to LLRB trees. Covered in these slides:

https://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf

A simpler implementation of red-black trees. Came across it and enjoyed it.

MaxScheiber• 10 years ago

I haven't actually found LLRBs to be simpler to implement, and a couple other sources agree with me. They're pedagogically simpler than standard RB trees, but if your goal is to introduce students to a balanced binary tree, I'd argue that AVLs are easier to teach and implement than either RBs or LLRBs.

http://t-t-travails.blogspot.com/2008/04/left-leaning-red-bl...

http://www.read.seas.harvard.edu/~kohler/notes/llrb.html

foliveira• 10 years ago

In the HyperBitBit initial experiments slide, the table with the results and estimates is throwing me off guard in regard to the ratios.

From my quick calculations, I'm getting [1.03, 0.96, 0.96, 1.05] but the table specifically has [1.05, 1.03, 0.96, 1.03]

Am I missing something here? Specifically the 2M case has a positive ratio when the HBB estimate is higher than the actual count.

brilee• 10 years ago

I had an opportunity to dig into the details of hyperloglog recently, and I wrote up my results here - http://moderndescartes.com/essays/hyperloglog

HyperLogLog is definitely one of the most elegant algorithms I'm aware of. The only thing is that the problem it solves is very specific, and it's hard to generalize it to do other things.

antirez• 10 years ago

Sedgewick is a very good writer IMHO. I learned algorithms with his famous book "Algorithms in C". Later I read many different algorithms books, and there are better books from specific point of views, however as an entry level book I think that AiC is one of the most accessible for students.

Btw, Redis recently switched from HyperLogLog to the slightly better LogLog-Beta algorithm which is not listed in this publication AFAIK.

pselbert• 10 years ago

Redis recently switched from HyperLogLog to the slightly better LogLog-Beta

Interesting, has anything been written about that? I've learned most of what I know about cardinality estimation from Redis and your writing on the matter, so I'd love to see more. It would be great to re-visit an article I wrote about HLL[0] from a new perspective as well.

[0] https://blog.codeship.com/counting-distinct-values-with-hype...

octernion• 10 years ago

See the Arxiv paper[0] on it.

Found this from the Redis code[1] (I was curious, too).

[0] https://arxiv.org/abs/1612.02284

[1] https://github.com/antirez/redis/blob/87538cb7fe19b567118944...

oertl• 10 years ago

If you are interested in new cardinality estimation algorithms for HyperLogLog sketches you could also have a look on the paper I am currently working on:

http://oertl.github.io/hyperloglog-sketch-estimation-paper/

There, I present two different algorithms based on theoretical considerations that are both accurate over the entire cardinality range. Unlike LogLog-Beta or HyperLogLog++, they do not need any empirically determined coefficients or bias correction data.

barrkel• 10 years ago

This presentation is from 2016, not 2011.

Cardinality Estimation (2011) [pdf]

Related Stories