<p>Daniel Lemire has a couple of papers on pre-sorting to increase compression and performance.
Here's the latest: <a href="http://arxiv.org/abs/1207.2189" rel="nofollow">http://arxiv.org/abs/1207.2189</a></p>

<p>You might look at his EWah variant as well. </p>

<p>The prevailing feeling is that Bitmap array compression techniques work great when the dataset changes slowly as most implementations discard and rebuild the index on each change. For datasets that change more often, traditional index approaches (such as B-Tree variants) are still king.</p>

<p>Implementations: <a href="https://github.com/lemire/javaewah" rel="nofollow">https://github.com/lemire/javaewah</a> and <a href="https://github.com/lemire/EWAHBoolArray" rel="nofollow">https://github.com/lemire/EWAHBoolArray</a></p>
Modifying WAH Compress bitmap performence
<p>I have developing word align bitmap compression algorithm for data indexing.algorithm is based on the WAH compression research paper.compression bitmap perform well on bit-wise operation and it's very space efficient. but modifying the compressed bitmap not very efficient ,because modifying need splitting compressed word size block and several memmove cause performance bottleneck. </p>

<blockquote>
  <p>please look at the following example.</p>
  
  <p>example: data set -
  [1000000,34,9,23456,6543,10000000,23440004,100,345]</p>
</blockquote>

<p>performance reduce  due to the random nature of the data set , in the real application scenario this can happened.</p>

<ol>
<li>can anyone give me a hint on how to overcome this performance problem?.</li>
</ol>