【免费】BetterbitmapperformancewithRoaringbitmaps_How to improve bitmap performance资源-CSDN下载

需积分: 0 171 浏览量 2023-03-06 08:33:18 上传评论收藏 345KB PDF 举报

Better bitmap performance with Roaring bitmaps 本文介绍了Roaring位图格式，这是一种压缩位图索引技术，旨在提高数据库和搜索引擎中的查询性能。通过对比Roaring位图与其他两种高性能的RLE（Run-Length Encoding）基于的位图编码技术WAH（Word Aligned Hybrid compression scheme）和Concise（Compressed ‘n’ Composable Integer Set），实验结果表明Roaring位图在压缩率和查询速度方面都有所提高。 1. 位图索引简介位图索引是一种常用的数据库和搜索引擎技术，通过位级并行运算可以明显地加速查询速度。但是，位图索引也可以占用大量内存空间，于是压缩位图索引是非常必要的。Oracle公司率先使用RLE对位图索引进行压缩，然而本文提出了Roaring压缩位图格式，使用打包数组进行压缩而不是RLE。 2. Roaring位图格式 Roaring位图格式使用打包数组进行压缩，而不是传统的RLE方式。这种方法可以更好地压缩位图索引，提高查询速度。 3. 实验结果在合成和真实数据上的实验结果表明，Roaring位图格式可以压缩率提高2倍，查询速度提高900倍以上。这些结果挑战了RLE基于的位图压缩技术是最好的观点。 4. 位图索引的应用位图索引广泛应用于数据库和搜索引擎中，如Java平台（java.util.BitSet）中也使用了位图索引。当集合S的基数相对宇宙大小n较大时（例如|S| > n/64 on 64-bit processors），位图索引通常优于其他可比的数据结构。 5. 位图索引的优点位图索引有两个主要优点：压缩率高和查询速度快。通过使用Roaring位图格式，可以更好地压缩位图索引，提高查询速度。 6. 结论本文提出了Roaring压缩位图格式，使用打包数组进行压缩。实验结果表明Roaring位图格式可以压缩率和查询速度方面都有所提高。这些结果挑战了RLE基于的位图压缩技术是最好的观点。因此，Roaring位图格式可以应用于数据库和搜索引擎中，以提高查询性能。

资源推荐

资源详情

资源评论

Better bitmap performance with Roaring bitmaps

S. Chambi

, D. Lemire

, O. Kaser

, R. Godin

Département d’informatique, UQAM, Montreal, Qc, Canada

LICEF Research Center, TELUQ, Montreal, QC, Canada

Computer Science and Applied Statistics, UNB Saint John, Saint John, NB, Canada

SUMMARY

Bitmap indexes are commonly used in databases and search engines. By exploiting bit-level parallelism,

they can signiﬁcantly accelerate queries. However, they can use much memory, and thus we might prefer

compressed bitmap indexes. Following Oracle’s lead, bitmaps are often compressed using run-length

encoding (RLE). Building on prior work, we introduce the Roaring compressed bitmap format: it uses

packed arrays for compression instead of RLE. We compare it to two high-performance RLE-based bitmap

encoding techniques: WAH (Word Aligned Hybrid compression scheme) and Concise (Compressed ‘n’

Composable Integer Set). On synthetic and real data, we ﬁnd that Roaring bitmaps (1) often compress

signiﬁcantly better (e.g., 2×) and (2) are faster than the compressed alternatives (up to 900× faster for

intersections). Our results challenge the view that RLE-based bitmap compression is best.

KEY WORDS: performance; measurement; index compression; bitmap index

1. INTRODUCTION

A bitmap (or bitset) is a binary array that we can view as an efﬁcient and compact representation

of an integer set, S. Given a bitmap of n bits, the i

bit is set to one if the i

integer in the range

[0, n − 1] exists in the set. For example, the sets {3, 4, 7} and {4, 5, 7} might be stored in binary

form as 10011000 and 10110000. We can compute the union or the intersection between two

such corresponding lists using bitwise operations (OR, AND) on the bitmaps (e.g., 10111000 and

10010000 in our case). Bitmaps are part of the Java platform (java.util.BitSet).

When the cardinality of S is relatively large compared to the universe size, n (e.g., |S| > n/64

on 64-bit processors), bitmaps are often superior to other comparable data structures such as

arrays, hash sets or trees. However, on moderately low density bitmaps (n/10000 < |S| < n/64),

compressed bitmaps such as Concise can be preferable [1].

Most of the recently proposed compressed bitmap formats are derived from Oracle’s BBC [2] and

use run-length encoding (RLE) for compression: WAH [3], Concise [1], EWAH [4], COMPAX [5],

VLC [6], VAL-WAH [7], etc. Wu et al.’s WAH is probably the best known. WAH divides a bitmap

of n bits into



w−1



words of w − 1 bits, where w is a convenient word length (e.g., w = 32).

WAH distinguishes between two types of words: words made of just w − 1 ones (11· · · 1) or just

w − 1 zeros (00· · · 0), are ﬁll words, whereas words containing a mix of zeros and ones (e.g.,

101110· · · 1) are literal words. Literal words are stored using w bits: the most signiﬁcant bit is

set to zero and the remaining bits store the heterogeneous w − 1 bits. Sequences of homogeneous

ﬁll words (all ones or all zeros) are also stored using w bits: the most signiﬁcant bit is set to 1, the

∗

Correspondence to: Daniel Lemire, LICEF Research Center, TELUQ, Université du Québec, 5800 Saint-Denis, Ofﬁce

1105, Montreal (Quebec), H2S 3L5 Canada. Email: [email protected]

Contract/grant sponsor: Natural Sciences and Engineering Research Council of Canada; contract/grant number: 261437

arXiv:1402.6407v9 [cs.DB] 28 Mar 2015

2 S. CHAMBI, D. LEMIRE, O. KASER, R. GODIN

second most signiﬁcant bit indicates the bit value of the homogeneous word sequence, while the

remaining w − 2 bits store the run length of the homogeneous word sequence.

When compressing a sparse bitmap, e.g., corresponding to the set {0, 2(w − 1), 4(w − 1), . . .},

WAH can use 2w bits per set bit. Concise reduces this memory usage by half [1]. It uses a similar

format except for coded ﬁll words. Instead of storing the run length r using w − 2 bits, Concise uses

only w − 2 − dlog

(w)e bits, setting aside dlog

(w)e bits as position bits. These dlog

(w)e position

bits encode a number p ∈ [0, w). When p = 0, we decode r + 1 ﬁll words. When it is non-zero, we

decode r ﬁll words preceded by a word that has its (p − 1)

bit ﬂipped compared to the following

ﬁll words. Consider the case where w = 32. Concise can code the set {0, 62, 124, . . .} using only

32 bits/integer, in contrast to WAH which requires 64 bits/integer.

Though they reduce memory usage, these formats derived from BBC have slow random access

compared to an uncompressed bitmap. That is, checking or changing the i

bit value is an O(n)-

time operation. Thus, though they represent an integer set, we cannot quickly check whether an

integer is in the set. This makes them unsuitable for some applications [8]. Moreover, RLE formats

have a limited ability to quickly skip data. For example, suppose that we are computing the bitwise

AND between two compressed bitmaps. If one bitmap has long runs of zeros, we might wish to

skip over the corresponding words in the other bitmap. Without an auxiliary index, this might be

impossible with formats like WAH and Concise.

Instead of using RLE and sacriﬁcing random access, we propose to partition the space [0, n)

into chunks and to store dense and sparse chunks differently [9]. On this basis, we introduce a new

bitmap compression scheme called Roaring. Roaring bitmaps store 32-bit integers in a compact

and efﬁcient two-level indexing data structure. Dense chunks are stored using bitmaps; sparse

chunks use packed arrays of 16-bit integers. In our example ({0, 62, 124, . . .}), it would use only

≈ 16 bits/integer, half of Concise’s memory usage. Moreover, on the synthetic-data test proposed

by Colantonio and Di Pietro [1], it is at least four times faster than WAH and Concise. In some

instances, it can be hundreds of times faster.

Our approach is reminiscent of O’Neil and O’Neil’s RIDBit external-memory system. RIDBit

is a B-tree of bitmaps, where a list is used instead when a chunk’s density is too small. However

RIDBit fared poorly compared to FastBit—a WAH-based system [10]: FastBit was up to 10× faster.

In contrast to the negative results of O’Neil et al., we ﬁnd that Roaring bitmaps can be several

times faster than WAH bitmaps for in-memory processing. Thus one of our main contributions is

to challenge the belief—expressed by authors such as by Colantonio and Di Pietro [1]—that WAH

bitmap compression is the most efﬁcient alternative.

A key ingredient in the performance of Roaring bitmaps are the new bit-count processor

instructions (such as popcnt) that became available on desktop processors more recently (2008).

Previously, table lookups were often used instead in systems like RIDBit [11], but they can be

several times slower. These new instructions allow us to quickly compute the density of new chunks,

and to efﬁciently extract the location of the set bits from a bitmap.

To surpass RLE-based formats such as WAH and Concise, we also rely on several algorithmic

strategies (see § 4). For example, when intersecting two sparse chunks, we may use an approach

based on binary search instead of a linear-time merge like RIDBit. Also, when merging two chunks,

we predict whether the result is dense or sparse to minimize wasteful conversions. In contrast,

O’Neil et al. report that RIDBit converts chunks after computing them [11].

2. ROARING BITMAP

We partition the range of 32-bit indexes ([0, n)) into chunks of 2

integers sharing the same 16 most

signiﬁcant digits. We use specialized containers to store their 16 least signiﬁcant bits.

When a chunk contains no more than 4096 integers, we use a sorted array of packed 16-bit

integers. When there are more than 4096 integers, we use a 2

-bit bitmap. Thus, we have two types

of containers: an array container for sparse chunks and a bitmap container for dense chunks. The

4096 threshold insures that at the level of the containers, each integer uses no more than 16 bits: we

BETTER BITMAP PERFORMANCE WITH ROARING BITMAPS 3

Array of containers

Most signiﬁcant

bits: 0x0000

Cardinality: 1000

124

186

248

310

61 938

array container

Most signiﬁcant

bits: 0x0001

Cardinality: 100

array container

Most signiﬁcant

bits: 0x0002

Cardinality: 2

bitmap container

Figure 1. Roaring bitmap containing the list of the ﬁrst 1000 multiples of 62, all integers [2

, 2

+ 100)

and all even numbers in [2 × 2

, 3 × 2

either use 2

bits for more than 4096 integers, using less than 16 bits/integer, or else we use exactly

16 bits/integer.

The containers are stored in a dynamic array with the shared 16 most-signiﬁcant bits: this serves

as a ﬁrst-level index. The array keeps the containers sorted by the 16 most-signiﬁcant bits. We expect

this ﬁrst-level index to be typically small: when n = 1 000 000, it contains at most 16 entries. Thus

it should often remain in the CPU cache. The containers themselves should never use much more

than 8 kB.

To illustrate the data structure, consider the list of the ﬁrst 1000 multiples of 62, all integers

, 2

+ 100) and all even numbers in [2 × 2

, 3 × 2

). When encoding this list using the

Concise format, we use one 32-bit ﬁll word for each of the 1000 multiples of 62, we use two

additional ﬁll words to include the list of numbers between 2

and 2

+ 100, and the even numbers

in [2 × 2

, 3 × 2

) are stored as literal words. In the Roaring format, both the multiples of 62 and

the integers in [2

, 2

+ 100) are stored using an array container using 16-bit per integer. The even

numbers in [2 × 2

, 3 × 2

) are stored in a 2

-bit bitmap container. See Fig. 1.

Each Roaring container keeps track of its cardinality (number of integers) using a counter. Thus

computing the cardinality of a Roaring bitmap can be done quickly: it sufﬁces to sum at most



n/2



counters. It also makes it possible to support rank and select queries faster than with a

typical bitmap: rank queries count the number of set bits in a range [0, i] whereas select queries seek

the location of the i

set bit.

The overhead due to the containers and the dynamic array means that our memory usage can

exceed 16 bits/integer. However, as long as the number of containers is small compared to the total

number of integers, we should never use much more than 16 bits/integer. We assume that there are

far fewer containers than integers. More precisely, we assume that the density typically exceeds

0.1 % or that n/|S| > 0.001. When applications encounter integer sets with lower density (less than

0.1 %), a bitmap is unlikely to be the proper data structure.

The presented Roaring data layout is intentionally simple. Several variations are possible. For

very dense bitmaps, when there are more than 2

− 4096 integers per container, we could store the

locations of the zero bits instead of a 2

-bit bitmap. Moreover, we could better compress sequences

of consecutive integers. We leave the investigation of these possibilities as future work.

剩余10页未读，继续阅读

评论收藏

内容反馈

@SmartSi

粉丝: 1w+

Better bitmap performance with Roaring bitmaps

Displaying Bitmaps Efficiently

Better Bitmap Performance with Roaring Bitmaps (2014)-计算机科学

RoaringBitmap-0.5.11-API文档-中文版.zip

RoaringBitmap-0.7.45-API文档-中英对照版.zip

RoaringBitmap-0.7.45-API文档-中文版.zip

pg_roaringbitmap：PostgreSQLRoaringBitmap扩展

RoaringBitmap-0.5.11-API文档-中英对照版.zip

Python库 | pyroaring-0.3.0-cp39-cp39-macosx_10_14_x86_64.whl

RoaringBitmap：Java中更好的压缩位集

RoaringBitmap.zip

Bitmap压缩技术

RoaringBitmap, 在Java中，一个更好的压缩 bitset.zip

PyRoaringBitMap:一个高效且轻量级的32位整数有序集

redis-roaring:Redis咆哮的位图

RoaringBitmap-0.7.45.jar中文文档.zip

A Combobox with bitmaps

Go-roaring-Go包实现压缩的bitsets

rbitmap:roaringbitmap的位图工具

Android中Glide获取图片Path、Bitmap用法详解

DisplayingBitmaps

Bitmap 性能和原理研究.docx

Android Drawable Bitmap 相互转换

处理android bitmap oom

Android代码-将Bitmap整合在一起的一个库

bitmap上传图片demo

Android下利用Bitmap切割图片

Activity跳转时传递Bitmap对象

jmeter连接ck所需jar包

canvas 转换成bitmap

SpringBoot中的跨域问题解决办法-Cors

自然语言处理的前沿进展与挑战

最新资源