Roaring Bitmaps: Implementation of an Optimized Software Library (2018) [pdf]
arxiv.org
arxiv.org
I created something like this for our database engine, ElevateDB, in 2011 or so. It divides up the bitmap space for a signed, 32-bit integer (our engines are embedded and have a limit of High(Int) on the number of rows) into nodes and, optionally, has a parallel array in each node for attaching object instances to each bit. Originally I just used them for representing sets of rows, but once you start using sparse bitmaps like this, you realize that you can use them for all sorts of things. Now I use them in buffer managers and many other areas. They're extremely efficient at locating a given row/tuple by its integer ID.
Past discussion of Roaring bitmaps[0].
I find it interesting that there is no real comparison (at least under the publications at the home page[1]) between Roaring bitmaps and FastBit[2] except for this little quote from 'Better bitmap performance with Roaring bitmaps' [3]:
Our approach is reminiscent of O’Neil and O’Neil’s RIDBit external-memory system. RIDBit is a B-tree of bitmaps, where a list is used instead when a chunk’s density is too small. However RIDBit fared poorly compared to FastBit—a WAH-based system: FastBit was up to 10× faster. In contrast to the negative results of O’Neil et al., we find that Roaring bitmaps can be several times faster than WAH bitmaps for in-memory processing. Thus one of our main contributions is to challenge the belief—expressed by authors such as by Colantonio and Di Pietro [1]—that WAH bitmap compression is the most efficient alternative.
[0]: https://news.ycombinator.com/item?id=8796997
[1]: http://roaringbitmap.org/