RoaringBitmapについて少し勉強した

社内で使用されている高速省メモリなビット集合の実装であるRoaringBitmap (https://github.com/RoaringBitmap/RoaringBitmap)の解説 (https://arxiv.org/pdf/1402.6407.pdf)を読んだ。以下では32bit整数の集合を管理することを前提に話を進める。この実装のアイデアは全体の整数集合を最上位の16bitを共有する2¹⁶個の整数毎に分割したコンテナとして管理し、各コンテナ内部の要素数に応じて整数集合の管理方法を変更するという点。内部の要素数が4096個以上ならばビット集合で管理し、 それ以下ならば16bit整数のソート済みリストで管理する。このような場合分けを行うことによって一つの整数を16bit以下で表現できるようになる（実際にはデータ構造を管理するためのデータもあるがそれらは無視できるサイズ）。もちろん整数集合が密であれば一つの整数あたりのbit数はさらに小さくなる。ANDやORなどの論理演算は各コンテナ毎にANDやORを行ってそれを集約すれば可能。それぞれのコンテナ同士の論理演算はビット集合同士・ビット集合とソート済み配列・ソート済み配列同士の場合分けでやるだけ。やってることはシンプルだけど他のビット集合実装（例えばランレングスエンコーディングを使ったものなど）と比べて半分程度のサイズを実現し、ANDの処理が数百倍速くなることもあるらしい（圧縮・解凍をやるととても遅くなることがあるということらしい）。簡単なアイデアで高い性能を実現するいい話。最近のSIGMOD論文（http://db.ucsd.edu/wp-content/uploads/2017/03/sidm338-wangA.pdf）でも推されているようだ（これはRoaringBitmapのトップページで引用されている）。