31–40 of 61 posts
> 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.
I thought the trick was going to be indirection. sorted-list/bitmap/runs, in a two level tree. cool. it's technically missing sorted compliment-list, i.e. only the items that are missing, although worst case runs only use twice as much space, so more complexity without much savings, esp. considering real workloads performs better with sequential ids than random uuids because you use fewer pages further research inves…
https://github.com/apache/lucene/blob/84cae4f27cfd3feb3bb42d...
While Roaring Bitmap performs well on space saving with good performance, my gut feeling is there're better ways to achieve the same goals, especially it involving sorting on insertion and binary search on lookup, both on the sorted top level list and the sorted lower-bit integers.
Also it works well on 32-bit integers and probably 64-bit integers but it's not clear it can scale well beyond to bigger integers.
Nevertheless it's an excellent algorithm that works well in practice.
Can 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…
To de-serialize, read each container by reading its prefix length and its container id, and then read the rest of the container by the length. The top level list is sorted by the container id. It can be reconstructed by inserting the container id with the container memory pointer into the sorted list.
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. 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”.
Much of this is just threshold effects for algorithm performance, not special cases per se. You don't even need to have specific knowledge of the hardware as long as you can identify cross-over points where one algorithm starts significantly outperforming others. An old HPC trick is to write software that thoroughly measures several algorithm strategies on your specific hardware environment and then code-gens an algo…
It looks a bit too simplistic: Blocks with up to 4k items are stored as sorted lists. Having to insert in a sorted list up to 4k items seems very expensive to me.
> 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.
Maybe the author means they compress poorly under generic, common compression algorithms. This is an exotic compression.
I wouldn't use the word exotic but rather specialized and/or optimized.
Infact later versions of Roaring use run-length-encoding (RLE) containers in addition to array and bitmap containers which is a technique shared with more traditional/general compression algorithms.
In effect rather than achieving "very good" compression, Roaring is very close to "optimal" compression for sparse bitmaps.
Not .bmp bitmaps used to store photographic images as I would have guessed: > Bitmaps are arrays of bits used to store sets of integers. They work by setting the Nth bit when an integer N is in the set
Earlier quoted context omitted.
This article has a section titled "how Roaring bitmaps are represented in memory". I suggest you actually read the article, it will likely answer all your questions.
I was actually asking how they were serialized and stored on disk.
It's very simple actually. I worked on adding run container support which involved adding support for the newer serialization format in roaring-rs and it proved quite elegant.