I’ve just found the paper Tree Encoded Bitmaps, which describes a nice mechanism for comprising bitmaps, somewhat similar to Roaring. This is something I use a great deal at work, where we store bitmaps of Piper changelists.
However, reading the paper makes me realize I need to do some data analysis first. The compression scheme is highly reliant on runs of 1-bits. In Piper, approximately half the changelists are “OCLs” which are renumbered into “NCLs” at submit time. This generated a very interleaved pattern of zeros and ones. So before investing any time in implementation, I should see how many runs of one’s we actually have.
Jabbering Giraffe 