SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic

Bitmap index is widely used in archiving and searching of Internet traffic, which is an essential step for analyzing network events in the field of network forensics. However, bitmap index requires a large storage space for fast searching in archival data. As current state-of-the-art bitmap index compression techniques, various encoding algorithms have been proposed, e.g. WAH, PLWAH, COMPAX, etc. With the advantages of fast query speed and easy implementation, PLWAH is an outstanding encoding scheme to encode the sparse dirty bits in bitmap index. Unfortunately, for searching Internet traffic, the constructed bitmap index can be quite dense locally according to the statistics. This is because that Internet traffic are usually composed of the flows with the same five tuple (SrcIP, SrcPort, DstIP, DstPort, proto). In this paper, SPLWAH is proposed to adapt to Internet traffic based on PLWAH. In SPLWAH, a new codebook is introduced to fit the characteristics of Internet traffic. We also conduct several performance evaluation experiments based on real network flow data from CAIDA. The results show that SPLWAH reduces the space consumption with a factor of 20% or more without incurring extra encoding and decoding cost. This work also shows that the design space in bitmap index compression is still a fruitful unknown frontier and worth further exploring to adapt to the emerging data spaces.