一文读懂比BitMap有更好性能的Roaring Bitmap

山行AI

发布于 2020-11-26 15:23:22

7.6K0

发布于 2020-11-26 15:23:22

文章被收录于专栏：山行AI山行AI

本文译自论文：https://arxiv.org/pdf/1402.6407.pdf，主要讲述了Roaring bitmap相较其他压缩方案表现出来的优势，包括存取速度，内存占用，按位取交集和并集的效率等，并附有实际的测试比对。

前言

通过本文你能学到什么？

1.什么是bitmap？为什么使用bitmap？Roaring bitmap与其他bitmap编码技术相比有哪些优势？2.Roaring bitmap将32位无符号整数按照高16位分容器，即最多可能有216=65536个容器(container)，存储数据时，按照数据的高16位找到container（找不到就会新建一个），再将低16位放入container中。高16位又称为共享有效位，它用于索引应该到哪个容器中查找对应的数值，属于roaring bitmap的一级索引。3.Roaring bitmaps以紧凑高效的两级索引数据结构存储32位整数。高密度块使用位图存储;稀疏块使用16位整数的压缩数组。当一个块包含不超过4096个整数时，我们使用一个排好序的16位整数数组。当有超过4096个整数时，我们使用2^16 位的位图。为什么按4096作为阀值呢？仅仅是因为当数据块中的整数数量超过这个值之后，bitmap将比数组的内存使用率更高。

4.为了检查32位整数x是否存在，我们首先使用二进制搜索查找对应于x/2^16^ 的容器。如果找到位图容器，则访问第(x对2^16取模)位。如果找到数组容器，则再次使用二分搜索。同样地，我们插入和删除一个整数x。我们首先寻找相应的容器。当找到的容器是位图时，我们设置相应位的值并相应地更新基数。如果找到数组容器，则使用二分查找，然后执行线性时间插入或删除操作。在删除整数时，如果位图容器的基数达到4096，则该位图容器可能成为数组容器。在添加整数时，当数组容器的基数超过4096时，它可能成为位图容器。当发生这种情况时，将使用更新后的数据创建一个新的容器，同时丢弃旧的容器。将数组容器转换为位图容器的方法是创建一个用零初始化的新位图容器，并设置相应的位。要将位图容器转换为数组容器，我们使用优化算法提取集合位的位置。计算两个数组容器的交集时也是采取二分查找（要求数组中数值有序）。5.两个Roaring bitmap之间可以通过AND和OR位操作快速进行交集和并集计算。6.bitmap比较适用于数据分布比较稠密的存储场景中，对于原始的Bitmap来说，这就需要2 ^ 32长度的bit数组通过计算可以发现(2 ^ 32 / 8 bytes = 512MB), 一个普通的Bitmap需要耗费512MB的存储空间。因为redis的bitmap数据结构是用string实现的，其大小为512M，所以在redis中就存在这个问题。Roaring bitmap会对数据块的基数进行统计，当基数小于4096时会用一个数组来存储，当基数大于4096时对应的则是一个BitmapContainer。BitmapContainer存储空间恒定为8k，最大基数可达8 * 1024 * 8 = 65536个。每个long有64位，因此需要1024个long来提供65536个bit。每个BitmapContainer在构建时就会初始化长度为1024的long[]。这就意味着，不管一个BitmapContainer中只存储了1个数据还是存储了65536个数据，占用的空间都是同样的8kb。7. 经过测试对比后发现Roaringbitmap与其他bitmap压缩算法相比往往表现得更好。8. 原生的 RoaringBitmap 只存储整形数据，32 位的 RoaringBitmap 最大的数据存储量是 2147483647。像订单、流量这样的数据量可以采用 64 位的 RoaringBitmap，但在性能上 32 位的效率在同等条件下要优于 64 位。

概要

Bitmap索引经常被用在数据库和搜索引擎中。通过利用位级并级度的优势，它能够显著地加速查询。但是，它也有一个缺点，那就是会耗费更多的内存，因此我们可能更偏向于压缩的BitMap索引。在Oracle的领导下，位图通常使用运行长度编码(RLE)进行压缩。在先前工作的基础上，我们引入了Roaring Bitmap格式，它使用压缩数组而不是RLE。我们将其与两种基于RLE的高性能的bitmap编码技术进行了比较：WAH(Word Aligned Hybrid compression scheme) 和Concise((Compressed ‘n’ Composable Integer Set)。在创造的和真实的数据上，我们发现Roaring bitmaps经常比其他压缩方案表现的更好（２倍以上），而且比其他压缩方案更快（交集比较速度达到其他方案的900倍）。我们的结果向认为基于RLE的压缩方案最好的观点发起了挑战。

关键字： 性能；度量；索引压缩；bitmap索引

1. 介绍

我们可以把一个bitmap或者bitset看作是一个用高效紧凑的整数集S表示的二进制数组。给一个bitmap设置为n位，如果在[0,n-1]范围内的第i个整数存在于集合中，则第i位设置为1。例如，集合{3,4,7}和集合{4,5,7}可以以二进制存储为10011000和10110000。我们可以在位图(例如，10111000和10010000)上使用按位操作(or, AND)计算两个对应列表之间的并集或交集。bitmap是Java平台(java.util.BitSet)的一部分。

当S的基数相对于宇宙大小相对较大时，n(例如，在64位处理器上|S| > n/64 )，位图通常优于其他类似的数据结构，如数组、哈希集或树。然而，在中等密度的位图(n/10000<|S|<n/64)，压缩位图如Concise可以优先考虑[1]。

最近提出的大多数压缩位图格式都源自Oracle的BBC[2]，并使用运行长度编码(RLE)进行压缩：WAH [3], Concise [1], EWAH [4], COMPAX [5], VLC [6], VAL-WAH [7]等等。WAH可能是最著名的。WAH把一个n位的bitmap划分为[n/w-1] 个词，每个词占w-1位，其中w是一个相对便于操作的长度（２^n 例如w=32)。WAH区分了两种类型的词:仅由w - 1个1组成的词(11··1)或仅由w - 1个0组成的词(00···0)是fill words，而由0和1混合组成的词(例如，101110···1)是literal word。字面词使用w位进行存储：最有效的位存储０，剩余的w-1位存储"0"、"1"混合序列。相同的fill words序列(全为１或全为０)也使用w位进行存储：第一有效位存储１，第二有效位用于标识相同fill words序列的位值（即全为0还是全为1)，剩下的w-2位用于存储相同的fill words序列的运行时长度（即总共有多少个这种相同的fill words)。

当压缩稀疏位图时，例如，对应于集合{0，2（w-1），4（w-1），...。。。}，WAH[1]会在设置每位时使用2w位的空间(由于较稀疏，会产生较多的fill words序列，而对fill words序列没有做太多压缩，只是针对连续相同的fill words序列进行了压缩)。Concise把内存的使用减少了一半。除了fill words编码外，它使用了类似的编码格式，Concise[2]仅仅使用w-2-[log2(w)]位存储序列运行时长度替代了WAH中存储运行长度为r时使用的w-2位，同时它预留了[log2(w)]位作为位置位。这些[log2(w)]位编码了数字p，其中p是[0,w)集合的一个元素。当p=0时，我们解码为r+1个fill words。当它非零时，我们解码为r个fill words并将它的第（p − 1）位与其他位相比进行0、1反转。在Concise算法中，我们把bitmap看作是一个整数集合，也就是说如果此bitmap是一个literal word，那么位数则代表整数的个数，固定为31个；如果此bitmap是一个fill word，那么整数的个数为Count(31-bits group) * 31。考虑w = 32的情况。Concise可以对集合{0，62，124，。。。。}仅使用32位/整数，而WAH则需要64位/整数。

与未压缩的bitmap相比，这些来自BBC的压缩格式尽管减少了内存的使用，但是它们具有较慢的随机访问速度。也就是说，检查或更改第i位值是一个O(n)时间复杂度的操作。因此，尽管它们表示一个整数集，但我们不能快速检查集合中是否有整数。这使得它们不适用于某些应用程序[8]。此外，RLE格式快速跳过数据的能力有限。例如，假设我们正在计算两个压缩位图之间的位图。如果一个位图有长串的零，我们可能希望跳过另一个位图中相应的单词。如果没有辅助索引，对于WAH和Concise这样的格式，这可能是不可能的。

为了避免使用RLE和牺牲随机访问，我们提出将空间[0,n)划分为块，并以不同的方式存储稠密和稀疏块[9]。在此基础上，我们引入了一种新的位图压缩方案，称为Roaring。Roaring bitmaps以紧凑高效的两级索引数据结构存储32位整数。高密度块使用位图存储;稀疏块使用16位整数的压缩数组。在我们的例子中({0,62,124，…})，它将只使用16位/整数，Concise的内存使用的一半。此外，在Colantonio和Di Pietro[1]提出的合成数据测试中，它至少比WAH和Concise快四倍。在某些情况下，它可以快数百倍。

我们的方法让人想起了O’Nei和他的RIDBit外部内存系统。RIDBit是由bitmap组成的B树，当块的密度太小时使用列表代替。然而，与基于wah的系统[10]的FastBit相比，RIDBit的表现很差:FastBit的速度要快10倍。与O’Nei等人的负面结果相反，我们发现对于内存处理来说，Roaring bitmap可以比WAH bitmap快几倍。因此，我们的主要贡献之一就是挑战由Colantonio和Di Pietro[1]等作者所表达的WAH位图压缩是最有效的替代方案的观点。

Roaring bitmap性能的一个关键因素是新的位计数处理器指令(例如popcnt)，它最近在桌面处理器上可用(2008年)。以前，表查找通常在RIDBit[11]这样的系统中使用，但它们可能会慢几倍。这些新的指令允许我们快速计算新块的密度，并有效地从位图中提取set位的位置。为了超越基于RLE的格式，如WAH和Concise，我们还依赖于几种算法策略(见4)。例如，当计算两个稀疏块的交集时，我们可以使用基于二分搜索的方法，而不是像RIDBit那样的线性时间合并方法。此外，当合并两个块时，我们预测结果是密集还是稀疏，以减少浪费的转换。相比之下，O’Nei等人报告RIDBit在计算后转换块[11]。

2. Roaring bitmap

我们将32位索引的范围([0,n))划分为共享相同的16位最有效数字的2 ^16 个整数块。我们使用专门的容器来存储它们的16个最低有效位。当一个块包含不超过4096个整数时，我们使用一个排好序的16位整数数组。当有超过4096个整数时，我们使用2^16 位的位图。因此，我们有两种类型的容器:用于稀疏块的数组容器和用于密集块的位图容器。4096阈值确保在容器级别上，每个整数使用不超过16位:我们要么对超过4096个整数使用2^16位，或者使用小于16位/整数，或者恰好使用16位/整数。

这些容器存储在一个动态数组中，其中共享16个最有效位:这作为一个一级索引。数组保持容器按16位最有效位排序。我们希望这个第一级索引通常比较小:当n = 1 000 000时，它最多包含16个条目。因此，它通常应该保留在CPU缓存中。容器本身使用的内存不应该超过8 kB(container中处理的是低16位的数据)。

为了说明数据结构，考虑62倍数的前1000个的列表，所有整数[2^16, 2^16 + 100]和[2* 2^16,3

2 ^16)中的所有偶数。使用Concise的格式编码这个列表的时候,我们使用一个32位fill word来处理1000个62的倍数的数,我们使用两个额外的fill word包含数字的列表2 ^ 16和2 ^ 16 + 100之间的数,将偶数(2 * 2 ^ 16,3 * 2 ^ 16)存储为literal words。在Roaring格式中，62的倍数和[2^16,^ 2^16 + 100)中的整数都使用每个整数16位的数组容器存储。[2

2 ^16, 3 *2 ^16]中的偶数存储在一个16位的位图容器中。见图1。

每个Roaring的容器都使用计数器来跟踪其基数(整数的数目)。因此计算Roaring bitmap的基数能够很快完成：它最多加起来[n/2^16]个计数器就够了。它还使得支持排序和选择查询的速度比使用典型的位图更快成为可能：: rank查询计算范围[0,i]内集合位的数量，而select查询查找第i个集合位的位置。容器和动态数组带来的开销意味着我们的内存使用可以超过16位/整数。但是，只要容器的数量与整型数的总数相比很小，我们就不应该使用超过16位/整型的容器。我们假设容器的数量远远少于整数的范围。更准确地说，我们假设数据密度通常超过0.1%或n/|S|>0.001。当应用程序遇到密度较低的整数集(小于0.1%)时，位图不太可能是合适的数据结构。

本文提出的Roaring数据布局故意设计得很简单。有几种变体是可能的。对于非常密集的位图，当每个容器有超过2^16 -4096个整数时，我们可以存储0位的位置，而不是2^16位的位图。此外，我们可以更好地压缩连续整数序列。我们把对这些可能性的调查留作将来的工作。

3. 访问操作

为了检查32位整数x是否存在，我们首先使用二进制搜索查找对应于x/2^16^ 的容器。如果找到位图容器，则访问第(x对2^16取模)位。如果找到数组容器，则再次使用二分搜索。同样地，我们插入和删除一个整数x。我们首先寻找相应的容器。当找到的容器是位图时，我们设置相应位的值并相应地更新基数。如果找到数组容器，则使用二分查找，然后执行线性时间插入或删除操作。

在删除整数时，如果位图容器的基数达到4096，则该位图容器可能成为数组容器。在添加整数时，当数组容器的基数超过4096时，它可能成为位图容器。当发生这种情况时，将使用更新后的数据创建一个新的容器，同时丢弃旧的容器。将数组容器转换为位图容器的方法是创建一个用零初始化的新位图容器，并设置相应的位。要将位图容器转换为数组容器，我们使用优化算法提取集合位的位置(见算法2)。

4. 逻辑运算

我们在Roaring位图上实现了各种操作，包括并集(位OR)和交集(位AND)。两个Roaring bitmap之间的按位操作包括迭代和比较第一级索引上的16个高位整数(keys)。为了获得更好的性能，我们维护已排序的一级数组，在每次迭代中比较两个key。两个key相等时，在相应容器之间执行第二级逻辑操作，这总是生成一个新的容器。如果容器不为空，它将与公共键（高16位用于分桶的key）一起添加到结果中。然后，位于第一级数组上的迭代器加1。当两个键不相等时，包含最小键的数组增加一个位置，如果计算并集，则将最小的键和相应容器的副本添加到结果中。当进行并集计算时，我们一直重复直到两个一级数组用完为止。当进行交集计算时，一旦一个数组遍历完，我们就终止。

为了同样的优势，我们还维护数组容器的排序。由于容器可以用两种不同的数据结构(位图和数组)表示，两个容器之间的逻辑并集或者交集涉及以下三种场景之一:

Bitmap vs Bitmap: 我们迭代1024个64位的词。对于并集操作，我们执行1024个位OR操作并将结果写入一个新的位图容器中。参见算法1。得到的基数是使用java中的Long.bitCount进行高效计算的。

按位计算ORs和计算结果的基数似乎要比仅按位计算ORs慢得多。然而，有四个因素缓解了这个潜在的问题：

1.流行的处理器(Intel, AMD, ARM)有快速的指令来计算一个单词中的1的个数。Intel和AMD的popcnt指令的吞吐量高达每CPU周期一个操作。2.最近的Java实现将Long.bitCount调用转换成如此快速的指令。3.流行的处理器是超标量的:它们可以一次执行多个操作。因此，当我们检索下一个数据元素、按位计算它们并将其存储在内存中时，处理器可以对最后的结果应用popcnt指令并相应地增加基数计数器。4.对于廉价的数据处理操作，处理器可能由于缓存丢失而不能满负荷运行。5.在我们用于实验的Java平台上，我们估计可以以每秒7亿个64位词的速度计算和编写按位OR操作。如果我们进一步计算生成结果时的基数，估计速度会降至每秒5亿字左右。也就是说，由于保持基数，我们遭受了大约30%的速度损失。相比之下，像WAH和Concise这样的竞争方法在执行单个位操作之前必须花时间解码单词类型，这些检查可能会导致昂贵的分支错误预测或损害超标量的执行。

在计算交集时，我们使用一种不太直接的路径。首先，我们使用1024位AND指令来计算结果的基数。如果基数大于4096，那么我们继续进行并集操作，将按位ANDs的结果写入一个新的位图容器。否则，创建一个新的数组容器。我们使用算法2动态地从位ANDs中提取集合位。见算法3。

Bitmap vs Array: 当两个容器中的一个是位图容器，另一个是已排序动态数组时，交集可以非常快速地计算:迭代已排序的动态数组，并验证位图容器中每个16位整数的存在性。结果被写到数组容器中。并集也是有效的:我们创建位图的副本，并简单地遍历数组，设置相应的位。

Array vs Array: 对于并集，如果基数之和不超过4096，则在两个数组之间使用merge算法。否则，在位图容器中设置与两个数组对应的位，然后我们使用快速指令计算基数。如果基数不超过4096，我们将位图容器转换为数组容器(见算法2)。对于交集，当两者的基数差异小于64的因数时我们使用简单的merge(类似于在归并排序中所做的)。否则，我们使用galloping 进行交集计算 [8]。结果总是写入一个新的数组容器中。当一个数组(r)比另一个数组(f)小得多时，Galloping优于简单的合并，因为它可以跳过许多比较。从两个数组的开头开始，我们从小数组r中选择下一个可用的整数ri，并在大数组f中寻找至少与fj一样大的整数，首先查找下一个值，然后查找距离为其两倍的值，依此类推。然后，我们使用二分搜索将第二个列表向前推进到第一个大于或等于ri的值。

我们也可以在适当的地方执行其中的一些操作：

1.当计算两个位图容器之间的并集时，可以修改其中一个位图容器，而不是生成一个新的位图容器。类似地，对于两个位图容器之间的交集，如果结果的基数超过4096，则可以修改其中一个容器。2.当计算数组和位图容器之间的并集时，通过遍历数组容器的值并在位图容器中设置相应的位，可以将结果写入位图容器。通过检查word的值是否被修改，我们可以每次更新基数。

就地操作可以更快，因为它们避免了分配和初始化新的内存区域。

当聚合许多位图时，我们使用其他优化。例如，当计算许多位图的并集(例如，数百位图)时，我们首先找到具有相同键的所有容器(使用优先级队列)。如果一个这样的容器是位图容器，那么我们可以克隆这个位图容器(如果需要的话)，并计算这个容器与所有相应容器的并集。在本例中，基数的计算可以在最后执行一次。见算法4。

实验

我们进行了一系列的实验，将Roaring位图的时空性能与其他著名的位图索引方案(Java s BitSet, WAH和Concise)的性能进行比较。我们使用了由Colantonio和Di Pietro[1]提供的用于WAH和CONCISE(2.2版本)的Concise Java库。

我们的Roaring-bitmap实现的代码和数据在http://roaringbitmap.org/上免费提供。我们的软件经过了完全的测试，我们的Java库已经被主流数据库系统如Apache Spark[13]和Druid[14]采用。基准测试是在AMD FXTM-8150八核处理器上执行的，运行频率为3.60 GHz，内存为16 GB。我们在Linux Ubuntu 12.04.1 LTS上使用Oracle服务器JVM version 1.7。我们所有的实验都是在内存中进行的。

为了说明Java中的即时编译器，我们首先运行测试，而不记录计时。然后我们重复几次测试，并报告一个平均值。

5.1 模拟合成实验

我们开始复制Colantonio和Di Pietro的合成实验[1]。然而，尽管它们包含了诸如Java的 HashSet之类的替代数据结构，但为了简单起见，我们只关注位图格式。我们的结果与Colantonio和Di Pietro的结果基本一致，因为我们有一个更好的处理器。

根据两个合成数据分布生成了10 ^ 5整数的数据集：均匀和离散的Beta（0.5，1）分布。（Colantonio和Di Pietro将后者描述为Zipfian分布。）在四种密度d（从2 ^ -10到0.5）变化的情况下比较了这四个方案。为了生成整数，我们首先在[0，1）中伪随机地选择了一个浮点数y。当需要均匀分布时，我们将×maxc添加到集合中。在β分布的情况下，我们添加了[y ^ 2×max]。最大值max表示要生成的整数总数与集合的所需密度（d）之比，即：max = 105 / d。由于均匀分布和Beta（0.5，1）分布的结果通常相似，因此我们没有系统地介绍这两者。

我们强调，我们的数据分布和基准测试紧随Colantonio和Di Pietro的工作[1]。由于他们使用此基准来显示Concise优于WAH的优势，因此，我们认为使用自己的基准来评估针对Concise的建议是公平的。图2a和2b显示了Java的BitSet使用的平均位数以及三种将位图存储在集合中的位图压缩技术。在这些测试中，Roaring位图需要Concise占用50％的空间，而稀疏位图需要25％的WAH空间。即使在我们的测试中，即使对于密集位图，BitSet类也会使用更多的内存。这是由于其内存分配策略可在存储量增加时使基础数组的大小增加一倍是必须的。我们可以通过克隆新构建的位图来恢复浪费的内存。我们Roaring的位图实现具有trim方法，可用于获得相同的结果。在这些测试中，我们没有调用这些方法。我们还报告交集和并集时间。也就是说，我们获取两个位图，并生成一个表示相交或并集的新位图。对于BitSet，这意味着我们首先需要创建一个副本（使用clone方法），因为按位操作是就地的。图2c和2d表示平均时间（以纳秒为单位），以执行两组整数之间的相交和并集。对于所有测试密度的交集，Roaring位图的速度是Concise和WAH的×4 −×5倍。并集的结果相似，除了中等密度（2 ^ -5≤d≤2 ^ -4）之外，Roaring仅比Concise和WAH中等（30％）。在密集数据上，BitSet的性能优于其他方案，但在稀疏位图上，BitSet的速度要慢10倍以上。我们测量了每种方案将单个元素a添加到整数排序集合S中所需的时间，即：∀i∈S：a> i。图2e显示，Roaring所需的时间少于WAH和Concise。此外，与Roaring位图不同，WAH和Concise不支持以随机顺序有效地插入值。最后，我们测量了从一个随机选择元素中删除一个随机选择的元素所需的时间整数集（图2f）。我们观察到Roaring位图比其他两种压缩格式具有更好的结果。

5.2 真实数据实验

表I II显示了五个真实数据集的结果，这些数据集使用了早期对压缩位图索引[15]的研究。只有两个例外：

•我们只将1985年9月的数据用于天气数据集(其他人在[16]之前使用过的一种方法)，否则它对于我们的测试环境来说太大了。•我们省略了CENSUS2000数据集，因为它只包含在一个大宇宙(n = 37 019 068)中平均基数为30的位图。对于位图来说，这是一个不适合的场景。由于结构开销，Roaring bitmap使用的内存和Concise位图一样多。然而，当计算交集时，Roaring位图要快4倍。

数据集是按原样获取的:在建立索引之前，我们没有对它们排序。

对于每个数据集，都建立了位图索引。然后，我们从索引中选择200位图，使用类似于分层抽样的方法来控制属性基数的大范围。我们首先抽样200个属性，并进行替换。对于每个采样的属性，我们随机选择其中一个位图。使用200位图作为100对输入的100对AND和OR操作;表IIb和IIc显示了当Roaring被BitSet, WAH或Concise取代时，时间因子增加。(值低于1.0表示Roaring速度较慢。)表IIa显示了当Roaring被其他方法之一取代时存储因子的增加。

一般来说，Roaring bitmap总是比WAH和Concise更快。在两个数据集(CENSUS1881和WIKILEAKS)上，Roaring bitmap比BitSet快，同时使用更少的内存(少40个)。在另外两个数据集上，BitSet的速度是Roaring bitmap的两倍多，但它也使用了三倍的内存。当比较BitSet和Roaring bitmap的速度时，可以考虑Roaring bitmap预先计算块级别的基数。因此，如果我们需要聚合位图的基数，Roaring bitmap就有优势。在WIKILEAKS的数据集上，Concise和WAH提供了比Roaring更好的压缩(大约30%)。这是由于存在一个长时间的运行(11···1填充词)，Roaring bitmap不会压缩。

CENSUS1881数据集的结果是惊人的:Roaring比其他方法快了900倍。这是由于位图的基数有很大的差异。当稀疏的位图与稠密的位图取交集时，Roaring是特别有效的。

6. 结论

本文介绍了一种新的位图压缩方案——Roaring。它将位图集项存储为32位整数，存储在一个空间效率高的两级索引中。与两种有竞争力的位图压缩方案相比，WAH和Concise，Roaring通常使用更少的内存和更快。当数据是有序的，位图需要存储长期连续的值(例如，在WIKILEAKS数据集)，替代方案，如Concise或WAH可能提供更好的压缩比。然而，即使在这些情况下，Roaring也可能更快。在未来的工作中，我们将考虑进一步提高性能和压缩比。我们可以添加新类型的容器。特别是，我们可以使用快速封装技术来优化数组容器[17]的存储使用。我们可以在算法中使用SIMD指令[18,19,20]。我们还应该回顾除交集和并集之外的其他操作，比如阈值查询[21]。我们计划进一步研究在信息检索方面的应用。我们有理由感到乐观:Apache Lucene(从5.0版开始)已经采用了一种Roaring格式[22]来压缩文档标识符。

高低位实现

32位的RoaringBitmap获取高低16位的实现：

       public static RoaringBitmap addOffset(final RoaringBitmap x, int offset) {
          int container_offset = offset >>> 16;
          int in_container_offset = offset % (1<<16);
          ---------------------------------

64位的Roaring64NavigableMap获取高低32位的实现：

       @Override
        public void addLong(long x) {
          int high = high(x);
          int low = low(x);

        ---------------------

         private int low(long id) {
          return RoaringIntPacking.low(id);
        }

        private int high(long id) {
          return RoaringIntPacking.high(id);
        }

              /**
         * 
         * @param id any long, positive or negative
         * @return an int holding the 32 highest order bits of information of the input long
         */
        public static int high(long id) {
          return (int) (id >> 32);
        }

        /**
         * 
         * @param id any long, positive or negative
         * @return an int holding the 32 lowest order bits of information of the input long
         */
        public static int low(long id) {
          return (int) id;
        }

概要

REFERENCES

•Colantonio A, Di Pietro R. Concise: Compressed ’n’ Composable Integer Set. Information Processing Letters 2010; 110(16):644–650, doi:10.1016/j.ipl.2010.05.018.•Antoshenkov G. Byte-aligned bitmap compression. DCC’95, IEEE Computer Society: Washington, DC, USA, 1995; 476.•Wu K, Stockinger K, Shoshani A. Breaking the curse of cardinality on bitmap indexes. SSDBM’08, Springer: Berlin, Heidelberg, 2008; 348–365.•Lemire D, Kaser O, Aouiche K. Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering 2010; 69(1):3–28, doi:10.1016/j.datak.2009.08.006.•Fusco F, Stoecklin MP, Vlachos M. NET-FLi: On-the-fly compression, archiving and indexing of streaming network traffic. Proceedings of the VLDB Endowment 2010; 3(2):1382–1393, doi:10.14778/1920841.1921011.•Corrales F, Chiu D, Sawin J. Variable length compression for bitmap indices. DEXA’11, Springer-Verlag: Berlin, Heidelberg, 2011; 381–395.•Guzun G, Canahuate G, Chiu D, Sawin J. A tunable compression framework for bitmap indices. ICDE’14, IEEE, 2014; 484–495.•Culpepper JS, Moffat A. Efficient set intersection for inverted indexing. ACM Transactions on Information Systems Dec 2010; 29(1):1:1–1:25, doi:10.1145/1877766.1877767.•Kaser O, Lemire D. Attribute value reordering for efficient hybrid OLAP. Information Sciences 2006; 176(16):2304–2336.•O’Neil E, O’Neil P, Wu K. Bitmap index design choices and their performance implications. IDEAS’07, IEEE, 2007; 72–84.•Rinfret D, O’Neil P, O’Neil E. Bit-sliced index arithmetic. Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, SIGMOD ’01, ACM: New York, NY, USA, 2001; 47–57, doi:10.1145/375663. 375669.•Warren HS Jr. Hacker’s Delight. 2nd ed. edn., Addison-Wesley: Boston, 2013.•Zaharia M, Chowdhury M, Franklin MJ, Shenker S, Stoica I. Spark: Cluster computing with working sets. Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, HotCloud’10, USENIX Association: Berkeley, CA, USA, 2010; 10–10.•Yang F, Tschetter E, Léauté X, Ray N, Merlino G, Ganguli D. Druid: A real-time analytical data store. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD ’14, ACM: New York, NY, USA, 2014; 157–168, doi:10.1145/2588555.2595631.•Lemire D, Kaser O, Gutarra E. Reordering rows for better compression: Beyond the lexicographical order. ACM Transactions on Database Systems 2012; 37(3), doi:10.1145/2338626.2338633. Article 20. BETTER BITMAP PERFORMANCE WITH ROARING BITMAPS 11•Beyer K, Ramakrishnan R. Bottom-up computation of sparse and iceberg CUBEs. SIGMOD Record 1999; 28(2):359–370, doi:10.1145/304181.304214.•Lemire D, Boytsov L. Decoding billions of integers per second through vectorization. Software: Practice and Experience 2015; 45(1), doi:10.1002/spe.2203.•Polychroniou O, Ross KA. Vectorized bloom filters for advanced simd processors. Proceedings of the Tenth International Workshop on Data Management on New Hardware, DaMoN ’14, ACM: New York, NY, USA, 2014; 1–6, doi:10.1145/2619228.2619234.•Lemire D, Boytsov L, Kurz N. SIMD compression and the intersection of sorted integers. http://arxiv.org/ abs/1401.6399 [last checked March 2015] 2014.•Inoue H, Ohara M, Taura K. Faster set intersection with SIMD instructions by reducing branch mispredictions. Proceedings of the VLDB Endowment 2014; 8(3).•Kaser O, Lemire D. Compressed bitmap indexes: beyond unions and intersections. Software: Practice and Experience 2014; doi:10.1002/spe.2289. In Press.•Grand A. LUCENE-5983: RoaringDocIdSet. https://issues.apache.org/jira/browse/ LUCENE-5983 [last checked March 2015] 2014