大数据位图索引压缩算法调研分析

113 浏览量更新于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 ﬂow 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 trafﬁc data acquisition, index

storage, and query processing. There are two categories

of ﬂow data-acquisition, corresponding to two types

of data: (1) packet-level network data and (2) ﬂow-

level network data. A typical trafﬁc-archiving system

structure is shown in Fig. 3.

Figure 3 describes a typical trafﬁc 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/ﬂow capture

technologies

Internet trafﬁc’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 ﬂow 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 ﬂow 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 ﬂows in real time is a major challenge.

2.2.2 High-performance packet/ﬂow storage

technologies

In ITAS, packets and ﬂow 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/ﬂow 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

efﬁcient approach is using bitmap index which is a

special case of inverted index also widely used by

search engines. Bitmap Index is very efﬁcient in dealing

with the network ﬂow 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 efﬁcient index, the index space

should be fragmented (i.e., shard or segmentation),

and the index ﬁle 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 trafﬁc-archiving system.

剩余15页未读，继续阅读

weixin_38683848

粉丝: 4
资源: 950

大数据位图索引压缩算法调研分析

fastbit-aplwah:在任何对齐的长度和字长中自适应 PLWAH 拟合

一堆大数据 常用的库和数据结构 资源

2022最新大数据面试宝典.pdf

kingbase 创建位图索引

Oracle 索引之——位图索引

Oracle 什么是B树索引、位图索引、函数索引

位图索引的例子及sql语句

doris的布隆索引和位图索引区别

普通索引和位图索引有什么区别

Doris 位图索引

最新资源

一堆大数据常用的库和数据结构资源