Roaring Bitmapについて
1670 ワード
BitMap/BitSetはデータ照会に広く応用されているが、データの疎化によるメモリの浪費も無視できないため、圧縮BitMapの探索が行われており、WAH、EWAH、Roaring Bitmapなどが知られている.その中で最も性能が高く、最も広く応用されているのはRoaring Bitmapで、例えばSpark、Lucene、Redis、Influxdbなどの有名なプロジェクトでRoaring Bitmapの姿を見ることができます.次に、Roaring Bitmapがどのように実現されているかについて話します.
従来のBitMapでは、すべてのBitが1つのIntまたはLong配列に配置され、Roaring Bitmapでデータの高さ16ビットをスライスし、高さ16ビットが同じで統一されたスライスに落ち、各スライスの大きさは同じで、最大2 16 2^{16}216個の数を収容することができる.次に、実際の数に応じて適切な記憶方式を選択し、ここでの記憶方式をRoaring Bitmapではコンテナ(Container)と呼ぶ.2 16 2^{16}216個のBitは8 kbであり、Bitmapでは必ず8 kbメモリを占有するが、1枚のチップの下に1つのデータしかない場合、8 kbを占有する必要はない.例えば、すべてのデータが存在する、すなわち2^16ビットのBit全ビット1は、4 byteのみを占有する(65536,1)で表すことができる.そのため、3つの異なるContainerがあります.
1. ArrayContainer
この容器は、収納数が比較的少ない場合に適しており、同じスライスでも高さ16ビットが同じであるため、低い16ビットを記録するだけでよい.ArrayContainerは秩序あるchar[]を使用してデータを保存します.間違いなく、ビットではなくデータを保存する16ビット低いです.このデータの初期容量は4であり、その後徐々に増大する.配列が整列しているため、検索時に二分法でデータが存在するかどうかを検出します.配列長が4096を超えるとBitmapContainerに変換されます.長さ4096で8 kbを占有しているが、4096個の値しか記憶できない.
2. BitmapContainer
この容器は通常のBitmapと同様にLong配列によって65536個のbit値を保存するため、長さは1024であり、閾値を超える/縮小すると、長さは1024である.BitmapContainerとArrayContainerでは相互変換が可能です.
3. RunContainer
RunContainerのRunはストローク長圧縮アルゴリズム(Run Length Encoding)を指し,連続データに対して比較的良い圧縮効果がある.すべてのデータをshort[]で格納します.その原理は,連続して現れる数字に対して,初期数字と後続数のみを記録することである.例えば、
パフォーマンスとメモリについて
性能面で最も優れたC++バージョンのRoaring Bitmap、例えばSIMD加速ビット操作は、もちろんそれだけではありません.個人的には、データが密集しているかどうかにかかわらず、Bitmapよりも優れていると考えられています.
興味があれば優秀なJavaバージョンの実装を読んでみてくださいhttps://github.com/RoaringBitmap/RoaringBitmap
従来のBitMapでは、すべてのBitが1つのIntまたはLong配列に配置され、Roaring Bitmapでデータの高さ16ビットをスライスし、高さ16ビットが同じで統一されたスライスに落ち、各スライスの大きさは同じで、最大2 16 2^{16}216個の数を収容することができる.次に、実際の数に応じて適切な記憶方式を選択し、ここでの記憶方式をRoaring Bitmapではコンテナ(Container)と呼ぶ.2 16 2^{16}216個のBitは8 kbであり、Bitmapでは必ず8 kbメモリを占有するが、1枚のチップの下に1つのデータしかない場合、8 kbを占有する必要はない.例えば、すべてのデータが存在する、すなわち2^16ビットのBit全ビット1は、4 byteのみを占有する(65536,1)で表すことができる.そのため、3つの異なるContainerがあります.
1. ArrayContainer
この容器は、収納数が比較的少ない場合に適しており、同じスライスでも高さ16ビットが同じであるため、低い16ビットを記録するだけでよい.ArrayContainerは秩序あるchar[]を使用してデータを保存します.間違いなく、ビットではなくデータを保存する16ビット低いです.このデータの初期容量は4であり、その後徐々に増大する.配列が整列しているため、検索時に二分法でデータが存在するかどうかを検出します.配列長が4096を超えるとBitmapContainerに変換されます.長さ4096で8 kbを占有しているが、4096個の値しか記憶できない.
2. BitmapContainer
この容器は通常のBitmapと同様にLong配列によって65536個のbit値を保存するため、長さは1024であり、閾値を超える/縮小すると、長さは1024である.BitmapContainerとArrayContainerでは相互変換が可能です.
3. RunContainer
RunContainerのRunはストローク長圧縮アルゴリズム(Run Length Encoding)を指し,連続データに対して比較的良い圧縮効果がある.すべてのデータをshort[]で格納します.その原理は,連続して現れる数字に対して,初期数字と後続数のみを記録することである.例えば、
1, 10, 20,10, 31,2は1, 2, ..., 11, 20, 31, 32, 33を表す.runOptimize()メソッドを呼び出すと、RunContainerとのスペース占有サイズが比較され、RunContainerに変換するかどうかを選択します.パフォーマンスとメモリについて
性能面で最も優れたC++バージョンのRoaring Bitmap、例えばSIMD加速ビット操作は、もちろんそれだけではありません.個人的には、データが密集しているかどうかにかかわらず、Bitmapよりも優れていると考えられています.
興味があれば優秀なJavaバージョンの実装を読んでみてくださいhttps://github.com/RoaringBitmap/RoaringBitmap