Paper Info
Title
Masc: A Bitmap Index Encoding Algorithm For Fast Data Retrieval
Abstract
The fast retrieval in archival traffic data is essential for network security and forensic analysis. A bitmap index is a data structure enabling fast search over large data collections in a limited time, but the space consumption is always a problem. WAH, PLWAH and COMPAX are proposed for compressing bitmap indexes for less storage. In this paper, a new bitmap index encoding scheme, named MASC, is proposed to further improve the compression ratio without impairing the query performance. Instead of being limited to a fixed length (31 bits) in PLWAH and COMPAX, the stride size can be as long as possible to encode consecutive zero bits and nonzero bits in a more compact way. Instead of piggyback used in PLWAH, a new structure in MASC called carrier is introduced as piggyback in PLWAH only carries an individual nonzero bit. We also generalize the traditional literal word concept in PLWAH and COMPAX. The validity of MASC encoding scheme is demonstrated with the application in Internet Traffic Archival system. Based on experiments with real Internet traffic data set from CAIDA, MASC has a better compression ratio than PLWAH and COMPAX2 without the penalty in query performance.
Year
DOI
Venue
2016
10.1109/ICC.2016.7510827
2016 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC)
Keywords
Field
DocType
traffic archival, network forensic, network security, bitmap index encoding, bitmap index compression, PLWAH, COMPAX
Data structure,ENCODE,Bitmap index,Data retrieval,Computer science,Network security,Computer network,Compression ratio,Internet traffic,Encoding (memory)
Conference
ISSN
Citations 
PageRank 
1550-3607
0
0.34
References 
Authors
13
9
Name
Order
Citations
PageRank
Yuhao Wen1121.75
Han Wang200.34
Zhen Chen321836.23
Junwei Cao493570.95
Guodong Peng570.95
Wen-Liang Huang670.95
Ziwei Hu700.68
Jing Zhou800.34
Jinghong Guo900.34