Roaring Bitmap
非負整数値の集合(重複のないsorted list)を圧縮して表現する手法の一つ 手法の紹介
上位bitを使ってブロックに分割
ブロック内の各要素の下位bitをconventionalな手法を使って表現する
Denseなブロックではbit vector
Sparseなブロックではsorted list
下位16 bitで分割することが多い
その場合4096 (= 2^12) 以上でbit vectorの方が空間効率がよくなるので、4096をdense or sparseの閾値にする
関連手法
Bitmapは連続する0が多く、run-length encoding (RLE) のような一般的な圧縮手法は圧縮には有効なのだが、例えば所属性チェックするにも全体を展開する必要があり、検索などに用いるデータ構造には適していない
一方Roaring Bitmapであれば、所属性のチェックは特定のブロックを読むだけでいい
ブロック分割を行うというアイデアはかなり昔 (Elias-Fano) に古典的な手法で提案されており、Roaring Bitmapはブロック内のcardinalityで表現方法を変えるというのが差分になっている なんでroaringなのか => よくわからない
利用例
Lucene 5からFilter cacheで利用
この実装ではさらに2^16 - 2^12以上のcaridinalityのブロックではビット反転してlistで保存するということもやっている
Lucene 7から一部インデックスフォーマットにもRoaring Bitmapにインスパイアされたデータ構造 (IndexedDISI) を使ってるらしい