COMBAT: a new bitmap index coding algorithm for big data

Yinjun Wu, Zhen Chen, Yuhao Wen, Wenxun Zheng, Junwei CaoTsinghua 2016 · DOI

Abstract

Bitmap indexing has been widely used in various applications due to its speed in bitwise operations. However, it can consume large amounts of memory. To solve this problem, various bitmap coding algorithms have been proposed. In this paper, we present COMbining Binary And Ternary encoding (COMBAT), a new bitmap index coding algorithm. Typical algorithms derived from Word Aligned Hybrid (WAH) are COMPressed Adaptive indeX (COMPAX) and Compressed “n” Composable Integer Set (CONCISE), which can combine either two or three continuous words after WAH encoding. COMBAT combines both mechanisms and results in more compact bitmap indexes. Moreover, querying time of COMBAT can be faster than that of COMPAX and CONCISE, since bitmap indexes are smaller and it would take less time to load them into memory. To prove the advantages of COMBAT, we extend a theoretical analysis model proposed by our group, which is composed of the analysis of various possible bitmap indexes. Some experimental results based on real data are also provided, which show COMBAT's storage and speed superiority. Our results demonstrate the advantages of COMBAT and codeword statistics are provided to solidify the proof.

Introduction

In the era of Big Data, efficient data retrieval is paramount. Applications ranging from IoT sensor networks to telecommunications generate massive datasets that require rapid querying. Bitmap indexing is a favored technique in these domains because it leverages hardware-level bitwise operations (AND, OR, NOT) for exceptional performance. However, raw bitmaps are notoriously memory-intensive, often exceeding the size of the original data.

To mitigate this, compression algorithms like Word Aligned Hybrid (WAH) were developed. WAH partitions bitmaps into "fills" (sequences of identical bits) and "literals" (mixed bit patterns). Subsequent improvements like CONCISE and COMPAX sought to further compress these indexes by merging contiguous words. Despite these advances, existing methods often fail to capture all possible optimization patterns, particularly in real-world data with irregular distributions.

The COMBAT Methodology

COMBAT (COMbining Binary And Ternary encoding) addresses these limitations by integrating the strengths of both binary and ternary merging strategies. While COMPAX focuses on merging three contiguous words (ternary) and CONCISE focuses on two (binary), COMBAT employs a more flexible vocabulary of codewords to maximize compression.

Comparison of WAH and COMPAX compression results.

As shown in the comparison between WAH and COMPAX, advanced algorithms can significantly reduce the number of codewords by identifying patterns across word boundaries. COMBAT extends this logic by introducing novel codeword types, such as the [NI2-LF] codeword.

Extracted figure from page 3 of COMBAT: a new bitmap index coding algorithm for big data

The [NI2-LF] codeword allows COMBAT to compress a literal containing two "dirty bytes" (bytes with set bits) followed by a fill. Most previous algorithms would treat such a literal as uncompressible if it contained more than one dirty byte. By recognizing these more complex patterns, COMBAT achieves a tighter index. Furthermore, COMBAT's codewords are versatile, capable of representing both 0-fills and 1-fills, as well as 0-literals and 1-literals, ensuring robust performance across diverse data distributions.

Experimental Results

The researchers evaluated COMBAT against WAH, CONCISE, and COMPAX using two large-scale real-world datasets:

  1. CAIDA 2013: Anonymized network traffic data with up to 13 million records.
  2. China Unicom CDR: Call Detail Records from a major wireless network.

Storage Efficiency

COMBAT consistently outperformed its predecessors, achieving approximately a 6% reduction in index size compared to COMPAX, which was previously the state-of-the-art. This reduction is attributed to COMBAT's ability to merge more varied word combinations that other algorithms overlook.

Query Performance and I/O

Query execution speed is directly linked to index size. Because COMBAT produces smaller indexes, it reduces the I/O overhead required to load data from disk into memory. On the China Unicom CDR dataset, COMBAT demonstrated a query speedup of up to 14%. On the CAIDA dataset, performance gains ranged from 1% to 7%. The time required to load indexes into memory was reduced by roughly 7%, mirroring the storage savings.

Conclusion

COMBAT represents a significant step forward in bitmap index compression. By combining binary and ternary encoding and introducing more sophisticated codeword patterns, it reduces the storage footprint and enhances query performance for Big Data applications. While the percentage gains may appear incremental, their impact at the zettabyte scale is substantial. Future work will explore hardware acceleration via GPUs and the integration of COMBAT into production-level analytics systems like Druid to further validate its utility in distributed environments.

Summary updated

Abstract

Bitmap indexing has been widely used in various applications due to its speed in bitwise operations. However, it can consume large amounts of memory. To solve this problem, various bitmap coding algorithms have been proposed. In this paper, we present COMbining Binary And Ternary encoding (COMBAT), a new bitmap index coding algorithm. Typical algorithms derived from Word Aligned Hybrid (WAH) are COMPressed Adaptive indeX (COMPAX) and Compressed “n” Composable Integer Set (CONCISE), which can combine either two or three continuous words after WAH encoding. COMBAT combines both mechanisms and results in more compact bitmap indexes. Moreover, querying time of COMBAT can be faster than that of COMPAX and CONCISE, since bitmap indexes are smaller and it would take less time to load them into memory. To prove the advantages of COMBAT, we extend a theoretical analysis model proposed by our group, which is composed of the analysis of various possible bitmap indexes. Some experimental results based on real data are also provided, which show COMBAT's storage and speed superiority. Our results demonstrate the advantages of COMBAT and codeword statistics are provided to solidify the proof.
BibTeX
@inproceedings{wu2016combat,
  author = {Yinjun Wu and Zhen Chen and Yuhao Wen and Wenxun Zheng and Junwei Cao},
  title = {{COMBAT: a new bitmap index coding algorithm for big data}},
  booktitle = {Tsinghua},
  year = {2016},
  doi = {10.1109/tst.2016.7442497},
}

Loading related content...

Figure