File RoaringBitmap.h

↰ Parent directory (ADS/set)

The compressed bitmap of Chambi, Lemire, Kaser and Godin (Roaring), beyond the book: a SET of integers of 32 bits [see File ADT.h], the engineered counterpart of the boolean vector of section 8.1 [see File BoolSet.h] for universes too large for a bit per integer and sets too dense for a sorted list [see File VectorIntersection.h].

Definition (ADS/set/RoaringBitmap.h)

Detailed Description

The universe is cut into chunks of :math:` 2^{16} ` integers by their top 16 bits, and each chunk that holds some item is a container of the low 16 bits of its items, kept in a vector sorted by the top bits:

  • an array container, the sorted array of the low bits, when the chunk holds at most 4096 items (2 bytes per item, at most 8 KB);

  • a bitmap container, the :math:` 2^{16} ` bits of the chunk in 1024 words (8 KB), when it holds more.

So no container takes more than 8 KB, and a set of n items takes at most about 2 n bytes and at most the bits of its universe, whichever is less. A search, an insertion and a removal find the container by a binary search with no branch on the chunks, kept apart in an array of their own, :math:` O( log c ) ` for c containers, and then search an array in the same way (or test a bit), and shift it (at most 4096 items, a few lines of cache) or set a bit; an array that passes 4096 items becomes a bitmap and a bitmap that falls to 4096 an array. The operations of two sets merge the vectors of the containers by their chunks and combine the containers of the same chunk:

  • two bitmaps word by word, the bits of the result counted in the same pass (4 words at a time with AVX2 [see File BoolSet.h]), a result of at most 4096 items then written as an array;

  • a bitmap and an array by testing, setting, clearing or flipping the bits of the array in a copy of the bitmap;

  • two arrays, with SSE4.2, by blocks of 8 items: for the intersection and the difference, a block of each array compared all against all by one comparison of strings (the method of Schlegel, Willhalm and Lehner), the items of the block of the first array found, or those not found in any block of the second one, packed by a shuffle and stored, and the block that ends first moving on; for the union, the two blocks merged by the network of minima and maxima of Inoue and Taura, the 8 smallest written but those equal to the one before them, and the next block taken from the array with the smaller head; for the symmetric difference, the union of the two differences (by a merge with no branch on short arrays); a union or a symmetric difference of more than 4096 items becoming a bitmap.

Compared with the literature: Roaring adds containers of runs (the intervals of consecutive integers, for sets with long runs) and the “lazy” unions of many bitmaps whose counts are computed at the end; the bitmaps of the other families (WAH, Concise, EWAH) compress runs of words and are slower to combine.

rank( x ), the items smaller than x, sums the counts of the containers before that of x and adds the place of x in it, :math:` O( c + 4096 ) `; select( i ) finds the container of the rank i by the same counts and the item in it; lowerBound( x ) starts an iterator at the first item not smaller than x.

The iterators visit the items in increasing order; an insertion or a removal invalidates them. The contracts [see File Contract.h]: after insert() the item is there and after remove() it is not; build() needs strictly increasing items, an audit; the invariant is that the containers are sorted by their chunks, not empty, arrays of at most 4096 sorted items and bitmaps of more, with their counts right, an O( n ) check at the level 3 on the sets of up to 4096 items. The operations are defined in RoaringBitmap.tpp.

  1. Chambi, D. Lemire, O. Kaser, R. Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience 46(5), 709-719, 2016, doi:10.1002/spe.2325

  1. Lemire, O. Kaser, N. Kurz, L. Deri, C. O’Hara, F. Saint-Jacques, G. Ssi-Yan-Kai, Roaring bitmaps: implementation of an optimized software library, Software: Practice and Experience 48(4), 867-895, 2018, doi:10.1002/spe.2560

  1. Schlegel, T. Willhalm, W. Lehner, Fast sorted-set intersection using SIMD instructions, Proceedings of ADMS 2011, 1-8, 2011

  1. Inoue, K. Taura, SIMD- and cache-friendly algorithm for sorting an array of structures, Proceedings of the VLDB Endowment 8(11), 1274-1285, 2015, doi:10.14778/2809974.2809988

  1. Muła, N. Kurz, D. Lemire, Faster population counts using AVX2 instructions, The Computer Journal 61(1), 2018, doi:10.1093/comjnl/bxx046

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes

Functions