Roaring bitmaps: what they are and how they work
vikramoberoi.com
Roaring bitmaps: what they are and how they work
1–10 of 61 posts
Re: Roaring bitmaps: what they are and how they work
#2I enjoyed this walkthrough. I'm interested in RB because it's used in Lucene but never dug in and assumed (without much thought) that it had to do with consecutive runs of 1s and 0s. Wrong!
Re: Roaring bitmaps: what they are and how they work
#3I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.
Re: Roaring bitmaps: what they are and how they work
#4I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.
I had the same takeaway when I read these papers. It felt like a game of whack-a-mole.
There's a massive performance benefit to doing this at the cost of implementation complexity. I haven't studied the implementations or tried my hand one, but I get the impression that these are tough to implement correctly in a way that takes full advantage of the hardware.
(In that sense, it's awesome that the researchers also did the legwork to implement and maintain a library!)
Re: Roaring bitmaps: what they are and how they work
#5Those who do not know judy1 are doomed to reinvent it.
Re: Roaring bitmaps: what they are and how they work
#6I enjoyed this walkthrough. I'm interested in RB because it's used in Lucene but never dug in and assumed (without much thought) that it had to do with consecutive runs of 1s and 0s. Wrong!
Compressing consecutive 1's and 0's was the first idea that popped into my head as well. Then when they started to talk about inserting into the 800,000th position my brain went "What if they just reversed the array and stored some metadata as the type of array they're dealing with?"
It's funny that in the end Bitmaps essentially are a modified data structure and process.
The way things are going, I imagine someone will at some point take all the different tricks we have of inserting, sorting, finding, deleting data, take millions of datasets and run some machine learning type process to create libraries that can perform these operations optimally.
Re: Roaring bitmaps: what they are and how they work
#7I enjoyed this walkthrough. I'm interested in RB because it's used in Lucene but never dug in and assumed (without much thought) that it had to do with consecutive runs of 1s and 0s. Wrong!
Compressing consecutive 1's and 0's was the first idea that popped into my head as well. Then when they started to talk about inserting into the 800,000th position my brain went "What if they just reversed the array and stored some metadata as the type of array they're dealing with?" It's funny that in the end Bitmaps essentially are a modified data structure and process. The way things are going, I imagine someone w…
I was thinking a similar thought that 4096 seemed quite magic (although it seems to be chosen based on research) and that RB perf could probably be tuned based on the workload
Re: Roaring bitmaps: what they are and how they work
#8I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics. Often they involve specific knowledge of the hardware instead of treating software as abstract. To me this is the big difference between “computer science” and “computer engineering”.
>I see this common theme among very fast practical algorithms (like timsort or pdqsort) where there is not some secret math or algorithm, rather they are just a bunch of special cases based on heuristics
The core here, which is bitmap storage and the basic optimization are simple, but solid and general. Mathematically it takes less space to store data as positions on a bitmap rather than fully spelt associations, and it takes even less space to seggregate the bitmaps in chunks.
This will hold and be smaller and faster in any computer. So, it's not some case of special case based on heuristics, either related to the specific frequencies or sample characteristics of some particular set of data, or of specific CPU peculiarities or whatever.
More exotic optimizations piled on top, sure. But "compressed bitmaps" themselves as a concept, not.
Re: Roaring bitmaps: what they are and how they work
#9> When a set is sparse, traditional bitmaps compress poorly.
They waste space. But if you were to compress them, they'd compress very well. As in, for example, if you were to compress them using roaring bitmaps.
Re: Roaring bitmaps: what they are and how they work
#10Can someone explain how this is laid out in memory and what it would look like serialized? It's easy to have an array of N size that fits all bits and just write to disk. You can also mmap a file as a large array of bytes and just mutate it and let the OS handle the disk syncs if you're okay with some data loss of recent state changes if the machine crashes.
What would an array of pointers to X containers which are N size each look like on disk?