大数据位图索引压缩算法调研分析
191 浏览量
更新于2024-07-14
收藏 2.11MB PDF 举报
"这篇研究论文深入探讨了大数据背景下位图索引压缩算法的现状与进展。随着互联网应用的普及和移动互联网的广泛使用，网络流量持续快速增长，这使得网络监控、故障排查和用户行为分析等领域对互联网流量存档系统（ITAS）的需求日益增加。在ITAS的三个关键技术中，位图索引压缩算法是本文的重点，对当前最先进的编码方案进行了详尽的综述。"
位图索引是一种高效的数据存储和检索技术，尤其适用于数据稀疏、维度较高的场景，如大数据环境中的实时查询。论文中提到的几种位图索引压缩算法包括：
1. **BBC (Block Bitmap Compression)**：一种基于块的压缩方法，通过将位图分割成固定大小的块并压缩每个块来节省存储空间。
2. **WAH (Word-Aligned Hybrid)**：此算法以单词对齐的方式进行压缩，允许在压缩位图中快速执行布尔运算。
3. **PLWAH (Packed-Word WAH)**：WAH的优化版，通过打包相邻的相同单词来提高压缩率。
4. **EWAH (Extended Word-Aligned Hybrid)**：进一步改进了WAH，通过消除前导零和后缀零来实现更高效的压缩。
5. **PWAH (Partitioned Word-Aligned Hybrid)**：一种将位图分成多个部分并分别压缩的方法，旨在提高处理效率。
6. **CONCISE (Combinatory Integer Sequence Compression)**：利用组合序列压缩技术，通过组合编码实现位图压缩。
7. **COMPAX**：结合多种压缩策略，如变长编码（VLC）和差分编码，以适应不同类型的位图数据。
8. **VLC (Variable-Length Coding)**：根据位的出现频率，使用不同长度的编码，降低存储需求。
9. **DF-WAH** 和 **VAL-WAH**：这两个算法是对WAH的变体，可能涉及差异编码或值编码，以改进压缩性能和查询效率。
论文中，作者根据不同的特征如分段、分块、合并压缩以及近似相等（Near Identical, NI）特性，对这些位图索引压缩算法进行了详细分类。此外，作者还提出了一些新的位图索引压缩思想，旨在进一步优化性能和压缩率，以应对大数据环境下的挑战。
位图索引压缩算法的研究对于大数据分析至关重要，因为它直接影响到数据的存储成本、查询速度和系统的整体性能。通过对现有算法的深入理解和比较，可以为未来的算法设计和优化提供参考，以满足不断增长的海量数据处理需求。
Zhen Chen et al.: A Survey of Bitmap Index-Compression Algorithms for Big Data 103
encoding in network flow archiving systems, and
gives a detailed survey on bitmap index compression
technology. Section 4 gives an outlook on the wide use
of bitmap index technology. We conclude the paper and
discuss future work in Section 5.
2 ITAS
2.1 ITAS structures and functions
ITAS, typically includes traffic data acquisition, index
storage, and query processing. There are two categories
of flow data-acquisition, corresponding to two types
of data: (1) packet-level network data and (2) flow-
level network data. A typical traffic-archiving system
structure is shown in Fig. 3.
Figure 3 describes a typical traffic archiving
system. After being captured, network data can be
routed to an index module in real time, or stored to disk
for subsequent processing. The index module updates
the index with the new data, typically compressing it
to reduce storage requirement. The indices are stored
by rows or columns after indices compression. In order
to reduce storage overhead, we adopt the method of
storage compression in the process of storage, such as
zip and LZO. When a query arrives, the query processor
looks up the current index and returns the corresponding
result.
2.2 Key technologies in ITAS
2.2.1 High-performance packet/flow capture
technologies
Internet traffic’s volume is very large, and still
growing. There are tens of millions of 64-byte packets
needed to deal with each second and similar orders of
magnitude of flow records from routers. In a 10 Gbps
link, for example, the network will reach 14 million
packets per second with 64 bytes per packet. Even after
aggregation, there are still millions per second. Though
only dealing with flow data, a backbone router’s
link of telecom operators would generate millions of
records per second which will reach 30 billion per
day
[10–13]
. Therefore, how to capture and store arriving
packets and flows in real time is a major challenge.
2.2.2 High-performance packet/flow storage
technologies
In ITAS, packets and flow records are stored in
relational databases by rows, and this consumes large
storage. Current distributed database systems have
begun to store the data in columns, compressing it
to reduce storage overhead. A popular compression
method is LZO (Lempel-Ziv-Oberhumer), known for
its focus on compression ratio. Other new methods
such as RasterZip and BreadZip
[14]
are proposed for
compression ratio and query performance.
2.2.3 High-performance packet/flow indexing
technologies
The accepted approach to indexing large volume of
data is to employ an inverted index, which is widely
used, for example, in search engines. However, a more
efficient approach is using bitmap index which is a
special case of inverted index also widely used by
search engines. Bitmap Index is very efficient in dealing
with the network flow queries, especially forensic
analysis. The “index space” for an enormous datastore
will explode; consequently, companies such as Google
have paid much attention to index compression
[15, 16]
. In
order to create an efficient index, the index space
should be fragmented (i.e., shard or segmentation),
and the index file should be compressed at the same
time. Bitmap compression algorithm is an effective
method for compressing the bitmap index, to solve the
Fig. 3 The structure of an Internet traffic-archiving system.
剩余15页未读，继续阅读
2021-06-22 上传
127 浏览量
165 浏览量
109 浏览量
109 浏览量
155 浏览量
104 浏览量
257 浏览量
点击了解资源详情
weixin_38683848
- 粉丝: 4
我的内容管理
展开
最新资源
- WebDrive v16.00.4368: 简易易用的Windows风格FTP工具
- FirexKit：Python的FireX库组件
- Labview登录界面设计与主界面跳转实现指南
- ASP.NET JS引用管理器：解决重复问题
- HTML5 canvas绘图技术源代码下载
- 昆仑通态嵌入版ASD操舵仪软件应用解析
- JavaScript实现最小公倍数和最大公约数算法
- C++中实现XML操作类的方法与应用
- 设计编程工具集：材料重量快速计算指南
- Fancybox：Jquery图片轮播幻灯弹窗插件推荐
- Splunk Fitbit：全方位分析您的活动与睡眠数据
- Emoji表情编码资源及数据库查询实现
- JavaScript实现图片编辑：截取、旋转、缩放功能详解
- QNMS系统架构与应用实践
- 微软高薪面试题解析：通向世界500强的挑战
- 绿色全屏大气园林设计企业整站源码与多技术项目资源
