大数据位图索引压缩算法研究

随着Internet应用程序的日益普及和移动Internet的广泛使用，过去二十年来Internet流量一直保持快速增长。 用于数据包或流记录的Internet流量归档系统（ITAS）已越来越广泛地用于网络监视，网络故障排除以及用户行为和体验分析。 在ITAS的三项关键技术中，我们重点研究位图索引压缩算法，并在本文中进行了详细的调查。 当前最新的位图索引编码方案包括：BBC，WAH，PLWAH，EWAH，PWAH，CONCISE，COMPAX，VLC，DF-WAH和VAL-WAH。 基于分段，分块，合并压缩和近乎相同（NI）功能的差异，我们对最新的位图索引压缩算法进行了彻底的分类。 我们还提出了一些新的位图索引编码算法，例如SECOMPAX，ICX，MASC和PLWAH +，并给出了其编码算法的状态图。 然后，我们使用来自CAIDA的真实Internet跟踪评估它们的CPU和GPU实现。 最后，我们总结并讨论了位图索引压缩算法的未来方向。 除了在网络安全和网络取证中的应用之外，具有更快的按位逻辑运算和减少的搜索空间的位图索引压缩还广泛用于基因组数据，地理信息系统，图形数据库，图像检索，物联网等的分析中。期望自1980年代以来，位图索引压缩将在大数据时代蓬勃发展并再次繁荣。