使用单个布隆过滤器，可以在给定的空间预算内近似地回答集合成员查询。实际系统通常使用布隆过滤器集合来支持数据跳跃、横向信息传递和网络过滤等应用。虽然现有工作深入优化了单个过滤器的空间与准确性分配，但如何在过滤器集合中联合优化空间使用仍是一个未被研究的问题。本次为大家带来数据库领域顶级会议VLDB 2024的文章《Optimizing Collections of Bloom Filters within a
Space Budget》。布隆过滤器在键值存储、数据跳过、查询优化和搜索引擎等场景中得到了广泛的应用，通过充当一种中间索引结构来减少存储读取，可以实现快速的数据加载。在布隆过滤器的一个典型使用场景中，一个数据量可能被划分在多个不同的文件中。假设一个用户想要查找符合特定条件（例如，通过社保号码识别的员工）的一条记录。一方面，我们可以简单地在每次查询时扫描整个数据量。该方法无需索引，但速度较慢。另一种方法是建立搜索键的索引，这可能需要大量额外空间，在某些环境（例如写密集型数据库或分布式系统）中难以实现。布隆过滤器可以在这两种极端之间找到平衡，为每个分区添加一个有限空间的过滤器，用于确定该分区是否需要处理——过滤器越大，跳过的精度越高。本案例展示了在实际应用中的布隆过滤器常使用过滤器集合（即，每个分区的过滤器）的方式来完成应用。现有方法是为集合中的每个过滤器设置相同的大小，但这种方法有几个关键缺陷。首先，单个布隆过滤器在插入数量不变的情况下保持固定大小，而过滤器集合的总大小会随着使用更多过滤器（例如，对数据的更多分区）而增长。如果我们希望将过滤器集合缓存到内存中，这种增长会成为一个问题。其次，并非所有分区都具有相同的查询概率，统一大小分配会给频繁查询的分区和稀有分区相同的精度。本文研究了以下问题：在给定预期的查询分布和总空间预算的情况下，能否优化每个过滤器的大小以最大化期望精度？而这一算法问题使得更广泛的数据检索架构成为可能。即实现一个固定大小的索引结构，其整体过滤精度会随着时间推移和数据增加而下降，但由于查询分布的已知偏斜（例如，偏向查询较新的过滤器），可以使得按查询权重加权的精度不会显著下降。这意味着，对于更频繁的查询，过滤器的准确性仍然较高，从而减少了假阳率的显著增加。本文提出了一些相关算法来实现这种架构，其创新点如下：1.本文提出了截断布隆过滤器通过布隆过滤器在构建后被截断来在空间和误报率中得到平衡。2.作者针对问题为一组截断布隆过滤器制定了一个约束优化问题，通过调整过滤器长度，减小使用更频繁的布隆过滤器的假阳率，并同时满足严格的bit级空间预算。3.本文证明了得到的优化问题与直觉相反，为凸优化问题并证明其具有线性时间的目标函数，并展示了其方法的有效性。• 布隆过滤器：布隆过滤器是一种概率性数据结构，用于表示集合，可以回答近似的成员查询。为了方便起见，本文中用B表示布隆过滤器。一个m-位的布隆过滤器B包含 n个元素，并且关联有k个独立的哈希函数 h1, h2, …, hk。我们将这些参数记为三元组 (m, k,n)。我们将使用符号 | · | 来表示布隆过滤器本身的大小。对于布隆过滤器来说，这一大小最初由参数m给出。记 q+ 为过滤器中的正键，q-为不在过滤器中的负键。布隆过滤器的设计使其具有误报率P(+ | q-) = 𝜀和零假阴率P(- | q+) = 0。误报率表示为：𝜀≈ (︁1 − (︁1 – 1 𝑚)︁𝑘𝑛)︁𝑘研究表明，这种表述是一个非常接近的近似值，但由于存在位独立性假设的缺陷，未能完全准确。如图1（c）所示，一旦接收到从前一阶段流出的k段，将k段分配到具有全局网格索引的相关网格。在处理“跨分区的轨迹”问题时，论文提出了一种剪枝策略来减少内存开销。同时，每个分区都建立一个本地索引来管理其分配的数据。随着k段流不断到达，两层索引是实时维护的。为了解决这个问题，本文引入了截断布隆过滤器。其基本思想是，布隆过滤器中先前分配的空间可以在之后撤销。这一概念有几个关键的好处。首先，它允许我们将优化问题视为先前分配空间的撤销；也就是说，本文可以从统一的空间分配开始，并根据优化目标移除位。其次，它允许布隆过滤器在在线环境中运行，可以不断添加新数据，但保持固定的存储大小。最后，它支持在整个过滤器集合中使用固定的哈希函数进行一致的查询。设B是一个具有m位、k个哈希函数和n个添加元素的布隆过滤器。一个截断布隆过滤器B’是通过从B中移除最右侧的m - m’位生成的。截断后的过滤器B’满足B’[1,2,…m’]= B[1,2,…,m’]。唯一的符号差异在于引入了一个新参数m’来指定截断后的过滤器长度。为了使这一定义可操作化，我们表明只需考虑在m’之前的哈希函数子集即可查询过滤器。本文称从宇宙集U中任意对象𝑜∈U到[m]的哈希函数ℎ𝑠 : U → [𝑚]为有效哈希函数，如果hS(o)≤ m’。称哈希函数为无效哈希函数，如果ℎ𝑠(𝑜) > 𝑚′，即哈希函数有效的条件是它映射到剩余区域；如果映射到截断区域，则为无效。除了退化情况外，截断布隆过滤器的假阳性率严格介于100%和原始假阳性率之间。为了直观地理解截断布隆过滤器的假阳性率，考虑图1中的第一个过滤器。这里4个哈希函数中只有3个是有效的，该示例中的假阳性率为(1 - (1 - 1 / m1)4*n1)3，这严格高于原始过滤器的假阳性率(1- (1-1
/ m1)4*n1)4。实际上，假阳性率是由有效哈希函数的数量决定的。在具体查询之前，我们无法确切知道有多少哈希函数是有效的。相反，我们定义了一个随机函数（称为假阳性函数）𝜙(·)，它返回一个表示假阳性率的随机变量。截断布隆过滤器的假阳性函数𝜙(V)定义为：
其中 V 是表示有效哈希函数数量的随机变量，范围𝑅𝑉 = {0}∪[𝑘]。给定一组k个独立且均匀的哈希函数 ℎ1, ..., ℎ𝑘，以及截断后剩余位数的比例𝑝 = 𝑚′ / m，假设位独立，截断布隆过滤器的假阳性率𝜀定义为：设B[1, 2, ..., m]是一个布隆过滤器，B′ = B[1, 2, ..., m′]是其截断的过滤器。设𝐻= {ℎ1,
..., ℎ𝑘}是过滤器B中使用的哈希函数集合。令 B′(𝑞)∈{−, +} 表示截断布隆过滤器的查询结果。假阳性率定义为𝜀 =Pr[B′(𝑞) = + | 𝑞 ∉ B]，其中 q 是不在布隆过滤器B中的键。从查询算法中可知，当对于H中的每个h，若ℎ(𝑞) ≤𝑚′则B′[ℎ(𝑞)] = B[ℎ(𝑞)] = 1时，B′(𝑞−) = +。设 I ⊆𝐻为哈希函数的一个子集，且令𝑞∉ B为过滤器中未存储的键。我们定义以下随机变量： • 𝐴I：对于𝑞∉ B如果⋀︁ℎ∈I B[ℎ(𝑞) = 1]，则𝐴I = 1，否则𝐴I = 0。 • 𝐶I：如果对每个ℎ ∈ I，ℎ(𝑞) ≤𝑚′且对于每个 ℎ ∈𝐻 \ I ，ℎ(𝑞) > 𝑚′，则𝐶I = 1，否则𝐶I = 0。本文正式定义了一个约束优化问题，该问题生成一个截断布隆过滤器的效用压缩草图。首先，本文证明了该优化问题是凸的，因此可以使用标准的凸优化算法来解决。接着，作者推导出一个松弛解，并证明该松弛解也是凸的。关键在于，这种松弛解在理论和实践中都可以比原问题更快地解决。基本的直觉是，一个假阳性率较高的过滤器被分配一个较低的效用值，而假阳性率较低的过滤器被分配一个较高的效用值。为了实现这种期望的属性，作者定义𝑢 · E[𝜙(𝑉)]。截断布隆过滤器的假阳性率通过在截断操作之前设定剩余位数𝑚′来调整。因此，我们的变量仅仅是整个布隆过滤器集合中截断过滤器的长度𝑚′1, 𝑚′2, ...,𝑚′𝑁。回到图1，可以看到效用值如何在优化过程中影响截断过滤器的长度。基于上述直觉，目标是通过找到截断过滤器长度的最佳分配，使效用值与假阳性率项的点积最小化，但需满足一些约束条件。首先，𝑚′𝑖的总和不能超过预算B。其次，每个𝑚′𝑖必须在0和原始过滤器长度𝑚𝑖之间。此约束优化问题定义如下：为了确立凸性，需要验证目标函数和约束函数都是凸的。通过检查，上述形式中的约束函数是线性的，因此是凸的。因此，只需确立目标函数的凸性。后续本文证明了假阳性函数为凸的，即：𝜙(𝑥) = (︁1 − (︁1 – 1 / 𝑚)︁𝑘𝑛)︁𝑥是凸的根据凸性的定义，即要证明二阶导数
是非负的。设𝑥≥ 0且 m, k, n > 0。定义𝑤 = 1 − (︁1 – 1 / 𝑚)︁𝑘𝑛，这由构造可知是一个严格正值。对函数进行二次求导得到：
因此，已证明在适当的条件下，截断布隆过滤器的假阳性函数是凸的。后续将证明一个关于目标函数凸性的更令人惊讶的结果。从二项式概率质量函数的图形可以直观上推测目标函数在优化变量中不太可能是凸的。然而，作者发现该函数确实是凸的。证明的结构基于二项分布是指数族分布的观察，这使我们能够利用该族分布的性质推导出目标函数是凸的，后续作者通过借助二项分布的指数组特性以及凸函数的非负加权和仍然保持凸性的性质证明了目标函数整体的凸性，其推导如下：目标函数的计算时间复杂度为O(𝑁 max𝑖∈ [𝑁] 𝑘𝑖) 。当目标函数的计算成本较高时，在空间中的高维点上计算梯度向量和Hessian矩阵的过程可能会成为许多凸优化求解器的关键瓶颈。在本文涉及的情境中，微分的线性特性表明底层求解器的运行时间将高度依赖于目标函数的时间复杂度。例如，梯度的每一项包含的求和操作会对应目标函数中对ki的内部求和。尽管这种运行时间对于许多应用来说是可以接受的，但在下一节中本文将探讨如何通过仅需线性时间 O(N) 的目标函数来找到接近最优解的近似解。本节描述了优化问题的一个松弛形式，其中使用了一个近似的目标函数。具体而言，这个目标函数是上一节中原始目标函数的下界。最小化下界时可以通过牺牲精确的最优解来简化并加速优化问题。这类下界方法通常应用于原始问题无法直接求解的情况下。作者发现，尽管原始问题是可以求解的，但最小化下界是一种在理论和实践中均有优势的解决方案。由于上述章节证明了𝜙是一个凸函数，作者利用詹森不等式，将假阳率写成以下的下界：
并证明了总体目标函数在m’上的凸性，并引入布隆过滤器假阳率近似进行进一步松弛。机器. 实验在一台配备8核Apple M3处理器、8 GB内存和512 GB SSD的机器上运行。实现方式. 方法研究原型使用Python 3.10编写。截断布隆过滤器使用了bitarray库构建。过滤器按照常用的标准流程构建。优化代码使用了CVXPY实现，最优解由内置的锥体求解器（ECOS）找到。ECOS是一种用于二阶锥规划的内点法。由于原始目标函数包含非凸的二项式概率质量函数，不符合DCP（结构化凸规划）要求，因此我们实现了松弛形式。此外，实施中还加入了预算相等约束，并使用取整函数将最优解映射到自然数。数据集. 本文在三个数据集上进行了评估，分别为：康涅狄格州房地产销售数据集（RE），华盛顿州电动汽车注册数据集（EV），NASA HTTP网络服务器日志数据集（NASA）。本文为每个数据集生成2500个符合上述结构的查询工作负载，选择最常用的谓词组合。对于给定的限制值 k ，通过完整扫描表并为每个查询计算每个记录的访问频率来确定记录的效用值。• 跳过率：查询跳过的分区数量与访问的总分区数量之比，即跳过/访问。• 浪费时间：因索引假阳性导致的浪费时间。当索引对某分区返回正结果，但查询结果为空时计入浪费时间。此指标是假阳性率的近似，也与谓词选择性相关。• 查询延迟：查询执行时间，包括从磁盘读取索引（如适用）、检查查询是否符合索引、从磁盘读取分区以及在分区上运行查询的时间。• 字母范围（R）：在每个分区内，按字典顺序排列属性值𝑦1≤𝑦2 ≤ ... ≤𝑦𝑙。查询属性值𝑦𝑞通过谓词𝑦1≤𝑦𝑞≤𝑦𝑙检查，若为真则读取分区，否则跳过。• 磁盘过滤器（D）：每个过滤器在磁盘上以全分辨率（即无截断）存储。访问分区时，将过滤器读入主存，然后对照索引检查查询。• 比例截断（PT）：每个过滤器按策略截断𝑚′𝑖 = ⌊𝐵 / 𝐹 · 𝑚𝑖⌋，其中F为全分辨率索引的大小。该方法类似于模块化布隆过滤器，即按照内存预算调整第一个模块的大小。• 高效用（TU）：应用类似于缓存驱逐策略（如最近最少使用或最少频率使用的策略。以效用降序将全分辨率过滤器逐步添加到缓存C中，直到达到预算，然后为剩余过滤器分配0位。该贪婪算法在满足∑︁ 𝑐∈𝐶𝑚𝑐≤𝐵.的条件下找到最大化∑︁ 𝑐∈𝐶𝑢𝑐的过滤器子集。• 弹性布隆过滤器（EBF）：创建7个缓存。对于每个0 ≤𝑗≤ 6，缓存 Cj 包含按截断策略构建的不同数量的过滤器单元𝑚′𝑖𝑗= ⌊𝑗 / 6 · 𝑚𝑖𝑗⌋。为确保在较大预算B下充分利用，仅启用最高层缓存数为ℎ = ⌈(1 – 𝐵 / 𝐹) · 6⌉。每个缓存分配等分预算𝐵′ = ⌊𝐵 / ℎ⌋。过滤器按效用从高到低添加至各层缓存直至达成缓存预算，剩余过滤器放入 C0 中。作者在如下任务中进行了后续试验证明其方法的优越性，具体分析如图：图2 在不同大小预算下，RE、EV和NASA数据集的平均跳过率（越高越好）从图2可以看到，本文的方法优于内存中的方法，并且与磁盘上的过滤器表现相似。图3 在不同索引大小预算B下，RE、EV和NASA数据集的平均浪费时间（越低越好）图4 在不同索引大小预算B下，RE、EV和NASA数据集的平均查询延迟（越低越好）。图6 在不同索引大小预算下，RE（左）和NASA（右）数据集上的混合内存和磁盘方法从图7可以看出，在较大预算下，本文的方法精度高于表现最好的对比方法（TMII），在较小预算下与其表现相当。本文提出了一种通过在效用分布上优化布隆过滤器集合，以满足空间预算的要求的方法。研究表明，在构建后对布隆过滤器进行截断会在精度和空间之间产生微妙的权衡，从而有利于优化。基于此，作者提出了截断布隆过滤器的结构，并设计了一个凸优化问题，并开发了一种快速的松弛方法来平衡这一权衡。从理论到实践的转变中，在两个不同的应用上展示了该方法能够有效缓解现有方法的局限性。
尚游 重庆大学计算机科学与技术专业2022级本科生，重庆大学Start Lab团队成员。 | 
|
重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有3~5名研究生名额，欢迎计算机、GIS等相关专业的学生报考！
图文｜尚 游
校稿｜朱明辉
编辑｜李佳俊
审核｜李瑞远
审核｜杨广超
