self-learning bitmap

[Chris Burroughs]

> Other alternative is self-learning bitmap
(http://ect.bell-labs.com/who/aychen/sbitmap4p.pdf) which, in my
understanding, is more memory efficient when counting small values.

In another thread on the Cassandra mailing list the topic of
self-learning bitmap's for cardinality estimation came up (thanks
Yuki!). This isn't one I've previously encountered during literature
search. Does anyone have any experience with them?

[Eugene Kirpichov]

I read through the article; the algorithm seems cool, extremely
efficient (a couple of additions/bit operations per item; not even
multiplications are needed) and plausible.

I didn't read into the analysis; I think I'll try implementing it and
experimenting with it.

--
Eugene Kirpichov
http://www.linkedin.com/in/eugenekirpichov

[Eugene Kirpichov]

...of course 1 hash per item is also needed.