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.
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.
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:
- 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.
- 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.
- 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