A survey of bitmap index compression algorithms for Big Data

Zhen Chen, Yuhao Wen, Junwei Cao, Wenxun Zheng, Jiahui Chang, Yinjun Wu, Ge Ma, Mourad Hakmaoui, Guodong PengTsinghua 2015 · DOI

Abstract

With the rapid growth of Internet traffic, Internet Traffic Archival Systems (ITAS) have become essential for network monitoring and forensic analysis. This paper surveys state-of-the-art bitmap index compression algorithms, including BBC, WAH, and CONCISE, and introduces four novel schemes: SECOMPAX, ICX, MASC, and PLWAH+. These algorithms leverage "Near Identical" (NI) bit patterns and GPU acceleration to address the "index-space explosion" problem. Evaluations using real Internet traces from CAIDA demonstrate that these new methods achieve up to 18% better compression and nearly 20x faster encoding speeds compared to traditional CPU-based implementations.

Introduction: The Data Deluge in Network Monitoring

As global Internet traffic scales toward the zettabyte era, the volume and velocity of streaming network packets present a significant challenge for archival and analysis systems. Traditional relational databases, often relying on B-tree indexing, struggle to keep pace with the high-speed ingestion requirements of modern 10 Gbps links.

Internet Traffic Archival Systems (ITAS) are designed to store and query these massive datasets. A typical ITAS architecture involves capturing real-time or historical data, indexing it for fast retrieval, and providing a query processor for analysis.

Architecture of network data indexing and storage systems.

Bitmap indexing has emerged as a powerful alternative for these systems. By representing the presence or absence of attributes as bits in a vector, it allows for high-speed bitwise logical operations (AND, OR, XOR) to resolve complex multi-dimensional queries. However, the primary drawback is "index-space explosion"—in sparse or high-cardinality datasets, the index can grow larger than the raw data. Efficient compression is therefore critical.

Categorizing Bitmap Compression Algorithms

Existing state-of-the-art algorithms like Word-Aligned Hybrid (WAH), Enhanced WAH (EWAH), and CONCISE are generally categorized based on four dimensions: segmentation, chunking, merge compression, and Near Identical (NI) features.

Building on this taxonomy, the researchers proposed four new algorithms designed to maximize both space efficiency and processing speed:

  • SECOMPAX: An evolution of the COMPAX algorithm that introduces "Nearly Identical Literals" (NI-L). This allows the system to compress words that contain very few "dirty" bits (bits that differ from the majority 0 or 1), which traditional algorithms would treat as uncompressible "Literal" words.
  • ICX (Improved COMPAX): This scheme extends compression capabilities to handle cases with two "dirty" bytes within a word, a scenario previously ignored by simpler word-aligned schemes.
  • MASC (Maximized Stride with Carrier): MASC represents a significant departure from the standard 31-bit "stride" found in WAH-based algorithms. By removing this fixed limitation, it can capture much longer runs of consecutive bits into a single compressed unit.
  • PLWAH+: This improves upon the Position List Word-Aligned Hybrid (PLWAH) scheme by adding a new "LF" word definition, allowing it to "piggyback" more NI words onto existing compressed runs.

Experimental Evaluation

The algorithms were evaluated using a real-world Internet traffic trace provided by CAIDA (Center for Applied Internet Data Analysis). The dataset consisted of over 13.5 million packets.

To test the indexing performance, the trace was converted into five-tuple bitmaps. These tuples typically include the Source IP, Destination IP, Source Port, Destination Port, and Protocol—fields found within the standard IPv4 and TCP headers.

Structure of an IPv4 packet header, showing the fields used to generate bitmap indices.

Before indexing, packets were reordered using locality-based hashing. This preprocessing step increases the "run lengths" of identical bits, which directly improves the effectiveness of the compression algorithms.

Key Results and Insights

The study yielded several critical insights into the future of bitmap indexing:

  1. The "Near Identical" Advantage: Real-world data is rarely "pure." By designing codewords that can handle "nearly clean" segments (e.g., a 32-bit word with only one or two bits flipped), the proposed algorithms significantly reduced the number of "Literal" words that typically bloat index sizes.
  2. Compression Performance: MASC emerged as the most efficient algorithm, reducing the index size for Source IP addresses by 16% to 18% compared to standard WAH and PLWAH.
  3. GPU Acceleration: Encoding is traditionally a serial, CPU-intensive task. By offloading these tasks to the GPU using the NVIDIA Thrust library, the researchers achieved massive parallelization. The GPU implementation of MASC was 19.5 times faster than the CPU version, reaching a throughput of over 3.4 million packets per second. This performance is sufficient to support real-time monitoring on 10 Gbps network links.

Conclusion and Future Work

While the proposed "Near Identical" schemes offer superior compression, future research must ensure that the increased complexity of these codewords does not negatively impact decoding and query processing speeds. Beyond network forensics, these bitmap compression techniques hold significant potential for other Big Data domains, including genome sequencing, Geographical Information Systems (GIS), and graph databases. As data volumes continue to explode, the evolution of bitmap indexing remains a vital area for high-performance data analysis.

Summary updated

Abstract

With the growing popularity of Internet applications and the widespread use of mobile Internet, Internet traffic has maintained rapid growth over the past two decades. Internet Traffic Archival Systems (ITAS) for packets or flow records have become more and more widely used in network monitoring, network troubleshooting, and user behavior and experience analysis. Among the three key technologies in ITAS, we focus on bitmap index compression algorithm and give a detailed survey in this paper. The current state-of-the-art bitmap index encoding schemes include: BBC, WAH, PLWAH, EWAH, PWAH, CONCISE, COMPAX, VLC, DF-WAH, and VAL-WAH. Based on differences in segmentation, chunking, merge compress, and Near Identical (NI) features, we provide a thorough categorization of the state-of-the-art bitmap index compression algorithms. We also propose some new bitmap index encoding algorithms, such as SECOMPAX, ICX, MASC, and PLWAH+, and present the state diagrams for their encoding algorithms. We then evaluate their CPU and GPU implementations with a real Internet trace from CAIDA. Finally, we summarize and discuss the future direction of bitmap index compression algorithms. Beyond the application in network security and network forensic, bitmap index compression with faster bitwise-logical operations and reduced search space is widely used in analysis in genome data, geographical information system, graph databases, image retrieval, Internet of things, etc. It is expected that bitmap index compression will thrive and be prosperous again in Big Data era since 1980s.
BibTeX
@inproceedings{chen2015survey,
  author = {Zhen Chen and Yuhao Wen and Junwei Cao and Wenxun Zheng and Jiahui Chang and Yinjun Wu and Ge Ma and Mourad Hakmaoui and Guodong Peng},
  title = {{A survey of bitmap index compression algorithms for Big Data}},
  booktitle = {Tsinghua},
  year = {2015},
  doi = {10.1109/tst.2015.7040519},
}
Figure