4 ms·

Roaring Bitmaps: Implementation of an Optimized Software Library (2018) [pdf]

39 points by espeed 8y ago

maxdemarzi 8y ago
Great Library. Available in most of the popular languages. I use it all the time to keep track of node ids instead of using sets of Longs. http://roaringbitmap.org/ http://roaringbitmap.org/
- TimJYoung 8y ago
  This is very true. 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.
kuwze 8y ago
Edit: I misspoke. It seems that they did a very thorough comparison with Word Aligned Hybrid compression scheme. I was just searching the PDFs for 'fastbit'. 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 https://news.ycombinator.com/item?id=8796997 [1]: http://roaringbitmap.org/ http://roaringbitmap.org/ [2]: https://sdm.lbl.gov/fastbit/ https://sdm.lbl.gov/fastbit/ [3]: https://arxiv.org/pdf/1402.6407.pdf https://arxiv.org/pdf/1402.6407.pdf
innagadadavida 8y ago
If you are using the Go port, do not do json marshal on the object, there is PR implementing it but is unmerged

39 points by espeed 8y ago

Great Library. Available in most of the popular languages. I use it all the time to keep track of node ids instead of using sets of Longs. http://roaringbitmap.org/ http://roaringbitmap.org/

TimJYoung 8y ago
This is very true. 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.

kuwze 8y ago

Edit: I misspoke. It seems that they did a very thorough comparison with Word Aligned Hybrid compression scheme. I was just searching the PDFs for 'fastbit'. 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 https://news.ycombinator.com/item?id=8796997 [1]: http://roaringbitmap.org/ http://roaringbitmap.org/ [2]: https://sdm.lbl.gov/fastbit/ https://sdm.lbl.gov/fastbit/ [3]: https://arxiv.org/pdf/1402.6407.pdf https://arxiv.org/pdf/1402.6407.pdf

innagadadavida 8y ago

If you are using the Go port, do not do json marshal on the object, there is PR implementing it but is unmerged