ConsistentlyFasterandSmallerCompressedBitmapswithRoaring-19thApril,2016(1603.06549)-计算机科学资源-CSDN文库

80 浏览量 2021-04-22 16:08:44 上传评论收藏 315KB PDF 举报

资源详情

资源评论

Consistently faster and smaller compressed bitmaps with Roaring

D. Lemire

, G. Ssi-Yan-Kai

, O. Kaser

LICEF Research Center, TELUQ, Montreal, QC, Canada

42 Quai Georges Gorse, Boulogne Billancourt, France

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

SUMMARY

Compressed bitmaps indexes are used in databases and search engines. A wide range of bitmap compression

techniques has been proposed, almost all relying primarily on run-length encoding (RLE), including BBC

and WAH. However, on unsorted data, we can get superior performance with a hybrid compression technique

that uses both uncompressed bitmaps and packed arrays inside a two-level tree. An instance of this technique,

Roaring, has recently been proposed. Due to its good performance, it has been adopted by several production

platforms (e.g., Apache Lucene, Apache Kylin and Druid).

Yet there are cases where run-length encoded bitmaps are smaller than the original Roaring bitmaps—

typically when the data is sorted so that the bitmaps contain long compressible runs. To better cope with

these cases, we build a new Roaring hybrid that combines uncompressed bitmaps, packed arrays and RLE

compressed segments. The result is a new Roaring format that compresses better.

Overall, our new implementation of Roaring can be several times faster (up to two orders of magnitude)

than the implementations of traditional RLE-based alternatives (WAH, Concise, EWAH) while compressing

better. We review the design choices and optimizations that make these good results possible.

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

1. INTRODUCTION

Sets are a fundamental abstraction in software. They can be implemented in various ways, as hash

sets, as trees, and so forth. In databases and search engines, sets are often an integral part of indexes.

For example, we may need to maintain a set of all documents or rows (represented by numerical

identiﬁer) that satisfy some property. Besides adding or removing elements from the set, we need

fast functions to compute the intersection, the union, the difference between sets, and so on.

To implement a set of integers, a particularly appealing strategy is the bitmap (also called bitset

or bit vector). Using n bits, we can represent any set made of the integers from the range [0, n): it

sufﬁces to set the i

bit is set to one if integer i is present in the set. Commodity processors use

words of W = 32 or W = 64 bits. By combining many such words, we can support large values of n.

Intersections, unions and differences can then be implemented as bitwise AND, OR and AND NOT

operations. More complicated set functions can also be implemented as bitwise operations [1].

When the bitset approach is applicable, it can be orders of magnitude faster than other possible

implementation of a set (e.g., as a hash set) while using several times less memory [2].

Unfortunately, conventional bitmaps are only applicable when the cardinality of the set (|S|) is

relatively large compared to the universe size (n), e.g., |S| > n/64. They are also suboptimal when

the set is made of a few ranges of consecutive values (e.g., S = {1, 2, 3, 4, . . . , 99, 100}).

∗

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

1105, Montreal (Quebec), H2S 3L5 Canada. Email: lemire@gmail.com

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

arXiv:1603.06549v2 [cs.DB] 19 Apr 2016

2 D. LEMIRE, G. SSI-YAN-KAI, O. KASER

One popular approach has been to compress bitmaps with run-length encoding. Effectively,

instead of using dn/W e words of W-bits for all bitmaps, we look for runs of consecutive words

containing only ones or only zeros, and we replace them with markers that indicate which value

is being repeated, and how many repetitions there are. This approach was ﬁrst put into practice by

Oracle’s BBC [3], using 8-bit words. Starting with WAH [4], there have been many variations on

this idea, including Concise [2], EWAH [5], COMPAX [6], and so on. (See § 2.)

When processing such RLE-compressed formats, one may need to read every compressed word

to determine whether a value is present in the set. Moreover, computing the intersection or union

between two bitmaps B

and B

has complexity O(|B

| + |B

|) where |B

| and |B

| are the

compressed sizes of the bitmaps. This complexity is worse than that of a hash set, where we can

compute an intersection with an expected-time complexity of O(min(|S

|, |S

|)) where |S

| and

| are the cardinalities of the sets. Indeed, it sufﬁces to iterate over the smallest sets, and for each

value, check whether it is present in the larger set. Similarly, we can compute an in-place union,

where the result is stored in the largest hash set, simply by inserting all of the values from the

small set in the large set, in expected time O(min(|S

|, |S

|)). It is comparatively more difﬁcult

to compute in-place unions with RLE-compressed bitmaps such as Concise or WAH. Moreover,

checking whether a given value is present in an RLE-compressed bitmap like Concise or WAH may

require a complete scan of the entire bitmap in O(|B|) time. Such a scan can be hundreds of times

slower than checking for the presence of a value in an uncompressed bitmap or hash map.

For better performance, Chambi et al. [7] proposed the Roaring bitmap format, and made

it available as an open-source library.

†

Roaring partitions the space [0, n) into chunks of

integers ([0, 2

), [2

, 2 × 2

), . . .). Each set value is stored in a container corresponding to

its chunk. Roaring stores dense and sparse chunks differently. Dense chunks (containing more than

4096 integers) are stored using conventional bitmap containers (made of 2

bits or 8 kB) whereas

sparse chunks use smaller containers made of packed sorted arrays of 16-bit integers. All integers in

a chunk share the same 16 most-signiﬁcant bits. The containers are stored in an array along with the

most-signiﬁcant bits. Though we refer to a Roaring bitmap as a bitmap, it is a hybrid data structure,

combining uncompressed bitmaps with sorted arrays.

Roaring allows fast random access. To check for the presence of a 32-bit integer x, we seek

a container corresponding to the 16 most signiﬁcant bits of x, using binary search. If a bitmap

container is found, we check the corresponding bit (at index x mod 2

); if an array container is

found, we use a binary search. Similarly, we can compute the intersection between two Roaring

bitmaps without having to access all of the data. Indeed, suppose that we have a Roaring bitmap

containing few values in the range [0, 2

),which implies it uses an array container. Suppose

we have another Roaring bitmap B

over the same range containing many values; it can only use a

bitmap container. In that case, computing the intersection between B

and B

can be done in time

O(|B

|), since it sufﬁces to iterate over the set values of B

and check whether the corresponding bit

is set in the bitmap container of B

. Moreover, to compute the in-place union of B

and B

, where

the result is stored in the large bitmaps (B

), it sufﬁces to iterate through the values of B

and set

the corresponding bits in B

to 1, in time O(|B

|). Checking whether a value is present in a Roaring

bitmap is relatively fast. It sufﬁces to locate the corresponding container (by a binary search). If the

container is a bitmap, a simple bit-value check sufﬁces, otherwise another binary search through a

packed array provides the desired answer.

Fast intersection, union and difference operations are made possible through fast operations

between containers, even when these containers have different types (i.e., bitmap-vs-bitmap, array-

vs-array, array-vs-bitmap, bitmap-vs-array). Though conceptually simple, these operations between

containers must produce new containers that are either arrays or bitmap containers. Because

converting between container types is potentially expensive, we found it useful to predict the

container type as part of the computation. For example, if we must compute the union between

two array containers such that the sum of their cardinalities exceed 4096, we preemptively create a

†

https://github.com/lemire/RoaringBitmap

ROARING: CONSISTENTLY FASTER AND SMALLER COMPRESSED BITMAPS 3

bitmap container and store the result of the union. Only if the resulting cardinality falls below 4096

do we convert back the result to an array container. (See § 5 for more details.)

We found that Roaring could compress better than WAH and Concise while providing superior

speed (up to two orders of magnitude). Consequently, many widely used systems have since adopted

Roaring: Apache Lucene [8] and its extensions (Solr, Elastic), Apache Kylin, Druid [9], and so forth.

However, Roaring has a limitation in some scenarios because it does not compress long runs of

values. Indeed, given a bitset made of a few long runs (e.g., all integers in [10, 1000]), Roaring—as

presented so far—can only offer suboptimal compression. This was reported in Chambi et al. [7]: in

one dataset, Concise and WAH offer better compression than Roaring (by about 30 %). Practitioners

working with Druid also reported to us that Roaring could use more space (e.g., 20 % or more) than

Concise. As previously reported [7], even when Roaring offers suboptimal compression, it can still

be expected to be faster for many important operations (see § 6.6). Nevertheless, there are cases

where storing the information as runs will both reduce memory usage drastically and accelerate

the computation. If we consider the case of a bitmap made of all integers in [10, 1000], Roaring

without support for runs would use 8 kB, whereas a few bytes ought to sufﬁce. Such unnecessarily

large bitmaps can stress memory bandwidth. Moreover, computing the intersection of two bitmaps

representing the ranges [10, 1000] and [500, 10000] can be done in a few cycles when using RLE-

compressed bitmaps, but the original Roaring would require intersecting two bitmap containers

and possibly thousands of cycles. Thus, there are cases where bitmaps without support for run

compression are clearly at a disadvantage and they are sometimes seen in practice.

To solve this problem, we decided to add a third type of container to Roaring, one that is ideally

suited to coding data made of runs of consecutive values. The new container is conceptually simple,

given a run (e.g., [10, 1000]), we simply store the starting point (10) and its length minus one (1000).

By packing the starting points and the lengths in pairs, using 16 bits each, we preserve the ability to

support fast random access by a binary search algorithm through the coded runs.

Adding a third container type introduces several engineering problems, however. For one thing,

instead of a handful of possible container type interactions (bitmap-bitmap, array-array and array-

bitmap), we have about twice as many (bitmap-bitmap, array-array, array-bitmap, run-bitmap, run-

array and run-run). Keeping in mind that we need to predict the container type as part of the

computation to avoid expensive container conversions, new heuristics are needed. It is also not a

priori clear whether introducing a new container type could comprehensively solve our compression

issues. Moreover, assuming that a new Roaring format improves compression, is it at the expense

of speed?

Thankfully, we are able to successfully implement a new Roaring model, made of three container

types, that is superior in almost every way to WAH, Concise and EWAH in all our tests—including

cases where the original Roaring performs more poorly. Compared to the original Roaring, the new

Roaring can improve the compression ratios by up to an order of magnitude. In what might be our

worst-case scenario (CENSUS1881), the new version has half the speed while saving only about 5%

of storage: even in this case, the new version remains faster by one or two orders of magnitude when

compared to an implementation of WAH and Concise. Thus we conclude that this new Roaring is

consistently faster and smaller than popular RLE-based compression schemes (WAH, Concise and

EWAH).

2. RELATED WORK

There are many RLE-based compression formats. For example, WAH organizes the data in literal

and ﬁll words. Literal words contain a mix of W − 1 zeros and ones (e.g., 01011 · · · 01) where

W denotes the processor word size in bits: typically W = 32 or W = 64. Fill words are made of

just W − 1 ones or just W − 1 zeros (i.e., 11 · · · 11 or 00 · · · 00). WAH compresses sequences of

consecutive identical ﬁll words. The most signiﬁcant bit of each word distinguishes between ﬁll and

literal words. When it is set to one, the remaining W − 1 bits store, literally, the W − 1 bits of a

literal word. When it is set to zero, the second most signiﬁcant bit indicates the bit value whereas

the remaining bits are used to store the number of consecutive identical ﬁll words (the run length).

4 D. LEMIRE, G. SSI-YAN-KAI, O. KASER

Concise is a variation that reduces the memory usage when the bitmap is sparse [2]. Instead of

storing the run length using W − 2 bits, Concise uses only W − 2 − dlog

(W )e bits to indicate a

run length r, reserving dlog

(W )e bits to store a value p. When p is non-zero, we decode r ﬁll words,

plus a single W − 1 bit word with its p

bit ﬂipped. Whereas WAH would use 64 bits per value

to store the set {0, 62, 124, . . .}, Concise would only use 32 bits per value.

EWAH is similar to WAH except that it uses a marker word that indicates the number of ﬁll

words to follow, their type, as well as the number of literal words to follow. Unlike WAH and

Concise, which represent the bitmap as a series of W − 1-bit words, EWAH uses W -bit words. The

EWAH format [5] supports a limited form of skipping because it uses marker words to record the

length of the sequences of ﬁll and literal words. Thus, if there are long sequences of literal words,

one does not need to access them all with EWAH when seeking data that is further along. Guzun et

al. [10] found that EWAH offers better speed than WAH and Concise.

The general idea behind Roaring—using different container types depending on the data

characteristics—is not novel. It is similar to O’Neil and O’Neil’s RIDBit external-memory system:

a B-tree of bitmaps, where a list is used instead when the density of a chunk is too small [11, 12].

Similarly, Culpepper and Moffat proposed a hybrid inverted index (HYB+M2) where some sets of

document identiﬁers are stored as compressed arrays whereas others are stored as bitmaps [13]. To

reduce cache misses, Lemire et al. partitioned the Culpepper-Moffat index into chunks that ﬁt in

L3 cache [14], effectively creating sets of bitmaps and arrays. Roaring is also reminiscent of C-

store where different columns are stored in different formats depending on their data characteristics

(number of runs, number of distinct values) [15]. It is likely that we could ﬁnd many similar

instances.

3. APPLICATION CONTEXT

Sets can be used for many purposes. We are interested by applications that use sets as part of an

index. For example, one might index an attribute in a database or a word in a set of documents.

Though we can expect updates, we assume that most of the processing is spent answering queries

that do not require modifying the set. Thus, our application setting is one that might be described as

analytical as opposed to transactional.

If we can assume that sets are immutable in the normal course of the application, this has the

added beneﬁt of simplifying parallelisation and concurrency. Moreover, the sets can be stored on

disk and memory-mapped on demand.

We need to provide functions that enable the creation of the sets, as well as their serialization

(for later reuse). Otherwise, we are most interested by the union and intersection between two or

more sets, as a new set. It is not uncommon to need to process many more than two sets at once.

We are also interested in random-value accesses, e.g., checking whether a value is contained in a

set—primarily because RLE-based schemes make these queries particularly expensive.

4. ROARING BITMAP

For a detailed presentation of the original Roaring model, we refer the interested reader to Chambi et

al. [7]. We summarize the main points and focus on the new algorithms and their implementations.

Roaring bitmaps are used to represent sets of 32-bit unsigned integers. At a high level, a Roaring

bitmap implementation is a key-value data structure where each key-value pair represents the set

S of all 32-bit integers that share the same highest 16 bits. The key is made of the shared 16 bits,

whereas the value is a container storing a list of the remaining 16 least signiﬁcant bits for each

member of S. In our actual implementation, the key-value store is implemented as two arrays: an

array of packed 16-bit values and an array of containers.

The arrays expand dynamically in a standard manner when there are insertions. Alternatively,

we could use a tree structure for faster insertions, but we expect Roaring bitmaps to be immutable

ROARING: CONSISTENTLY FASTER AND SMALLER COMPRESSED BITMAPS 5

for most of the life of an application. An array minimizes storage. In a system such as Druid, the

bitmaps are created, stored on disk and then memory-mapped as needed.

The structure of each container is straightforward (by design):

• A bitmap container is an object made of 1024 64-bit words (using 8 kB) representing an

uncompressed bitmap, able to store all sets of 16-bit integers. The container can be serialized

as an array of 64-bit words. We also use a counter to record how many bits are set to 1, and

this counter is kept up-to-date.

Counting the number of 1-bits in a word can be relatively expensive if done naïvely, but

modern processors have bit-count instructions—such as popcnt for x64 processors and cnt

for the 64-bit ARM architecture—that can do this count, sometimes using as little as a single

clock cycle. According to our tests, using dedicated processor instructions can be several times

faster than using either tabulation or other conventional alternatives [16]. Henceforth, we refer

to such a function as bitCount: it is provided in Java as the Long.bitCount intrinsic. We

assume that the platform has a fast bitCount function.

• An array container is an object containing a counter keeping track of the number of integers

followed by a packed array of sorted 16-bit unsigned integers. It can be serialized as a 16-bit

counter followed by the corresponding number of 16-bit values.

We implement array containers as dynamic arrays that grow their capacity using a standard

approach. That is, we keep a count of the used entries in an underlying array that has typically

some excess capacity. When the array needs to grow beyond its capacity, we allocate a larger

array and copy the data to this new array. Our allocation heuristic is as follow: when the

capacity is small (less than 64 entries), we double the capacity; when the capacity is moderate

(between 64 and 1067 entries), we multiply the capacity by 3/2; when the capacity is large

(1067 entries and more), we multiply the capacity by 5/4. Furthermore, we never allocate

more than the maximum needed (4096) and if we are within one sixteenth of the maximum

(> 3840), then we allocate the maximum right away (4096) to avoid any future reallocation.

A simpler heuristic where we double the capacity whenever it is insufﬁcient would be faster,

but it might use more memory than needed. When the array container is no longer expected

to grow, the programmer can use a trim function to copy the data to a new array with no

excess capacity.

• Our new addition, the run container, is made of a packed array of pairs of 16-bit integers. The

ﬁrst value of each pair represents a starting value, whereas the second value is the length of a

run. For example, we would store the values 11, 12, 13, 14, 15 as the pair 11, 4 where 4 means

that beyond 11 itself, there are 4 contiguous values that follow. In addition to this packed array,

we need to maintain the number of runs stored in the packed array. Like the array container,

the run container is stored in a dynamic array. During serialization, we write out the number

of runs, followed by the corresponding packed array.

Unlike array or bitmap containers, a run container does not keep track of its cardinality;

its cardinality can be computed on the ﬂy by summing the lengths of the runs. In most

applications, we expect the number of runs to be small: the computation of the cardinality,

when needed, should be fast.

No container ever uses much more than 8 kB of memory. Several such small containers ﬁt the L1

CPU cache of most processors: the last Intel desktop processor to have less than 64 kB of total (data

and code) L1 cache was the P6 created in 1995, whereas most mobile processors have 32 kB (e.g.,

NVidia, Qualcomm) or 64 kB (e.g., Apple) of total L1 cache.

When starting from an empty Roaring bitmap, if a value is added, an array container is created.

When inserting a new value in an array container, if the cardinality exceeds 4096, then the container

is transformed into a bitmap container. In reverse, if a value is removed from a bitmap container

so that its size falls under 4096 integers, then it is transformed into an array container. Whenever

a container becomes empty, it is removed from the top-level key-value structure along with the

corresponding key.

剩余20页未读，继续阅读

评论收藏

内容反馈

Consistently Faster and Smaller Compressed Bitmaps with Roaring ...

评论0

最新资源

Consistently Faster and Smaller Compressed Bitmaps with Roaring ...

评论0

最新资源

相关推荐

Learning Docker_Faster App Development and Deployment, 2nd-Packt(2017).pdf

Micro CMOS Design, 2012.pdf

java-javafx-sdk-13.0.2.zip

年度工作表现评估表-中英-Excel图表模板.xls

NGUI Next-Gen UI 3.0.7 f1.unitypackage

EhLib 8.0 Build 8.0.023 Pro Edition FullSource for D7-XE8

EhLib 9.1.024

EhLib 6.3 Build 6.3.176 Russian version. Full source included.

PHP.and.MySQL.Web.Development.5th.Edition

Fast and Robust Initialization for Visual-Inertial SLAM.pdf

ehlib_vcl_src_9_3.26

ethminer-0.16.0.dev3

Digital Electronics - A Practical Approach with VHDL, 9ed, 2012.pdf

Python & XML - XML Processing with Python, First Edition (2002).pdf

How.to.Use.Objects.Code.and.Concepts.0321995546

Spring.Essentials.178398

RxLib控件包内含RxGIF，全部源码及DEMO

人脸识别2019

BX2400 RF01 RF04_ RF08 各个系列的 .SchDoc .PcbDoc .pdf

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

VS2015安装证书，JavaScript_ProjectSystem.msi，JavaScript_LanguageService.msi

CANoe通过CAPL脚本实现自动测试

蓝牙BLE协议中文版.pdf

Qt 5实现串口调试助手（源工程文件、0积分下载）