Upbit with Parallelized Merge

Bitmap indexes use bit arrays or bit vectors and answer queries by performing bitwise logical operations on these bitmaps, which speed-up query processing. In order to min-imize storage space, bitmap indexes are stored in compressed form. Consequently, to perform insert operation, each one of the bitmaps needs to be updated to reflect a new row, which can be prohibitively costly. With regard to this bottleneck, researchers have come up with models like Update Conscious Bitmaps(UCB) [3], which uses Word Aligned Hybrid Encoding(WAH) [3]. UCB brings the concept of Existence Bitvector, which comes with a high probability of becoming uncompressible. Also it requires a lot of pointer maintenance for the updated rows. To overcome the above issues [2] introduces Upbit, which uses Update vectors for each bit vector. This makes updation easy as compared to the delete followed by insert technique used in UCB. It also increases the compressiblity of the bit vector becoming un-compressible by regularly merging the value and update bit vectors. But whenever this merging is done, that particular query is delayed. We propose to parallelize the task of merging value bit vectors and corresponding update bit vectors.