There are a lot of tools available in the "compressed bitmap" space. When last I needed something like this, I evaluated several approaches and ended up selecti

There are a lot of tools available in the "compressed bitmap" space. When last I needed something like this, I evaluated several approaches and ended up selecting Roaring Bitmaps: https://arxiv.org/abs/1402.6407 https://arxiv.org/abs/1402.6407 http://roaringbitmap.org http://roaringbitmap.org That application had some particular wins relating to large sparse bitmaps, especially the ability to efficiently perform binary operations directly on their compressed representations. I didn't need random insertions, so this ended up being a win across the board: faster runtime, lower memory footprint, and lower I/O requirements versus a normal bitset.