暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / L-FBF：用于键值存储的学习型功能Bloom过滤器

L-FBF：用于键值存储的学习型功能Bloom过滤器

时空实验室 2023-03-06
188
用学习模型来替代传统数据结构是一种具有挑战性的尝试，论文提出了一种用于键值存储的学习型功能Bloom过滤器（L-FBF）。在L-FBF中，学习模型学习给定数据的特征和分布，并对每个输入进行分类。理论分析表明，在相同的内存大小下，L-FBF比单个FBF的搜索失败率更低，同时提供了相同的语义保证。本次为大家带来的论文：《Learned FBF: Learning-Based Functional Bloom Filter for Key–Value Storage》

一．背景
最近的研究表明，与传统的数据结构相比，使用学习模型的新数据结构具有显著的优势。Bloom过滤器（BF）是用来指示一个输入是否是给定集合中的一个元素的传统二值分类数据结构，在给定的假阳性率下，学习型的BF比单个BF使用更少的内存，因此，基于学习的结构能够在内存需求和搜索失败方面提高性能。而键值数据结构返回一个键对应的值，高效的键值存储可以在有限的内存中存储大量数据，同时提供更好的性能。
论文认为学习模型可以取代键值存储的操作，同时提高搜索性能并节省内存。此外基于学习的方法通过利用精确单位数据分布信息来优化各种数据结构。但学习型Bloom过滤器只能解决存储成员关系信息的二分类任务，因此不用于键值数据结构。功能Bloom过滤器（FBF）作为Bloom过滤器的变体之一可以用作键值结构。FBF具有期望的特征，即它不会给插入的元素返回错误的值和不会产生假阴性。然而，它可能会返回假阳性和不确定的结果，从而导致搜索失败。
论文提出了L-FBF，一种学习型的功能Bloom过滤器，该模型可以应用于多分类任务。由于学习模型可能会产生假阴性或者错误分类的问题，所以论文提出的L-FBF由一个学习模型和两个小型的备份结构（假类结果Bloom过滤器（FR-BF）和一个验证功能Bloom过滤器（V-FBF））组成，以期望可以到达和FBF相同的效果。论文所提出的L-FBF结构有两个优点。首先是对于给定的内存大小，L-FBF通过在模型中添加FR-BF和V-FBF等辅助结构来达到比单一FBF更好的分类精度。此外，由于L-FBF的内存需求相当小且和数据大小无关，所以它对于大规模的数据更有效。
二．学习型功能Bloom过滤器
2.1 模型框架
通过将FBF的核心部分替换为一个学习模型，论文提出了一个学习型功能Bloom过滤器（L-FBF）来解决多分类问题，这是一种利用学习模型进行键值存储的高级FBF结构。但由于学习模型可能返回错误的分类结果或产生假阴性，因此构建L-FBF是具有挑战性的。
图1显示了所提出的学习型功能Bloom过滤器结构，它包括一个学习模型和两个小的附加结构：一个假类结果Bloom过滤器（FR-BF）和一个验证功能Bloom过滤器（V-FBF）

图1 总体框架图

2.2 学习模型
FBF可以被视为将每个输入分类为一个类的模型。换句话说，一个神经网络（NN）可以被用来取代一个FBF的核心部分。因为一个FBF有两个搜索失败的原因：假阳性和不确定性，当构建使用模型的L-FBF结构时，其主要目标是最小化搜索失败的概率。
当使用学习模型替代FBF时，该模型必须能够将属于集合S的元素和集外元素（属于Sc)区分开来，并将S中的元素分类到Sq，1≤q≤Q（Q是S中元素的类别数目），假设可以观察到每个类中元素的特定分布，并且Sc中包含的未来输入与测试集中的集外元素的分布相同，那么可以通过学习一个期望的哈希函数来构建一个FBF的模型。在这里，所需的哈希函数需要降低元素和集外元素之间哈希冲突以及不同类中的元素之间的哈希冲突。该函数可以在每个类中的元素之间或者集外元素之间有许多哈希冲突。
图2展示了一个用于多分类问题的神经网络，它使用分类交叉熵作为损失函数，softmax作为输出层的激活函数，输出的结果可以视为属于该类别的概率。其中集外元素也作为一类（负类），集合中的元素称为正类。因此类别总数为Q+1。类别0代表集外元素，Q是集合S中元素的类别数目。在图2中有两个正类。

图2 多分类的神经网络

为了保证不会产生假阴性或错误分类结果，论文在学习模型中分别添加了一个V-FBF和一个FR-BF。
2.3 V-FBF与FR-BF
V-FBF是根据从模型中返回的假阴性元素构建的。FR-BF用于指示一个正类输入是否被错误地分类，因此，FR-BF根据从模型中返回的具有错误结果的元素进行构建。具有错误结果的元素的返回给V-FBF，因此，V-FBF是由从模型中返回的假阴性元素和被错误分类的元素来的。此外，由于FR-BF的假阳性元素属于模型返回的真实类之一，V-FBF也由FR-BF返回的假阳性元素构建，以返回它们的实际类。
在该结构中，阈值τ被用来控制假阳率（FPR）。模型的输出可以被写为一个向量o=(o0,o1.....oQ)，其中o0是输入x被分类到Sc的概率（负类），oq是被分类到Sq的概率,，模型使用最大概率值oi作为预测的分类结果。然而如果最大概率值并没有和其他概率值有很大的差别，预测结果可能是不正确的。因此为了处理错误结果，尤其是控制假阳率，论文使用了阈值τ。当最大概率值oi大于等于τ时，返回类别i作为预测结果，否则，模型返回一个阴性结果。如果是假阴性，则可以被V-FBF纠正。为了降低FPR，应该设置一个较大的τ，这可能会导致模型出现更多的假阴性。
算法1展示了L-FBF结构的构造过程。首先针对给定的数据集S和Sctr（第2行）训练一个模型。Sctr是训练用的Sc的一个子集。模型的阈值τ是根据Scvd（是用于验证的Sc的一个子集）为所需的FPR (r)设置的。FR-BF是通过SFR（FR表示模型预测了一个不正确的正类且预测的类的概率大于或等于τ）中的元素构建的。V-FBF由SV中的元素构建，其中SV =SFR ∪SFN∪BFP，其中，FN表对于S中的一个正类元素模型预测了一个负类或模型输出的最大概率小于τ，BFP存放的是FR-BF中的元素。

图3说明了L-FBF的搜索过程。给定一个输入y，首先使用模型进行预测。如果模型返回一个负类，则查询V-FBF以确保没有假阴性，然后将V-FBF的结果作为预测类返回。如果模型返回预测类别q，则查询FR-BF来过滤错误分类结果。如果FR-BF返回一个正值，这意味着从模型返回的类是错误的，则查询V-FBF，然后将V-FBF的结果作为一个预测类别返回。否则，如果FR-BF返回一个负值，这意味着从模型返回的类是正确的，那么类q将作为预测结果返回。

图3 学习型功能Bloom过滤器的搜索过程

三．实验
由于论文的目的是用L-FBF代替FBF来提高性能，因此论文对所提出的L-FBF的性能进行了评估，并与单一FBF进行了比较。论文的实验数据集来自公开的数据集。对于正类集合，使用来自Curlie 的集合，这是为社区提供识别和分类其最佳内容的一个最大的人工编辑Web目录。正类集合包括485,423个两个类别的独特的白名单URLs。对于负类集，则使用来自Shalla的黑名单，这是一个公开的第三方黑名单资源。负数据集由1,491,178个独特的黑名单URLs组成。负集被随机分割以进行训练（81%）、验证（9%）和测试（10%）。因此，训练集包含所有的正类和81%的负类，测试集包含所有的正类和10%的负类（即在训练中或在验证中都不使用负类）。
假设学习模型的期望假阳性率（FPR）为0.005，并在模型训练后使用验证集设置FPR的阈值τ。在使用测试集测试L-FBF结构时，不确定性同时通过正输入和负输入报告，而假阳性仅通过负输入报告。
由于URLs是字符序列，RNNs能够对依赖时间和顺序的数据任务进行建模，因此论文首先考虑RNNs。然而，RNNs存在梯度消失的问题，这阻碍了对长数据序列的学习。门控循环单元（GRU）和长短期记忆（LSTM）是解决标准RNN中消失梯度问题的RNNs。GRU可以被认为是LSTM的一种变体。LSTM使用输入门、输出门和忘记门，而GRU使用更新门和复位门，这是两个向量，决定哪些信息应该传递给输出。GRU和LSTM的设计相似，效果很好，但GRU的参数比LSTM少。由于URLs在同一分量中的特征之间具有很高的相关性，而一维（1D）CNN对于从数据集的固定长度片段中提取特征非常有效，因此论文的实验还考虑了1D-CNN。
3.1 内存消耗
表1显示了各模型特征的比较。设nw表示模型中的权值个数，t为包含单个GRU层的模型的相对训练时间。包含两个GRU层（2- GRU）的模型由于有两个RNN层，其权重数最大。包含单个1D-CNN层的模型的训练时间最短，因为CNN的训练时间通常比RNN（即GRU和LSTM）要短。CNN的精度迅速提高，然后趋于稳定，而RNN的准确性在更长的训练迭代中继续略有提高。

表1 各模型的特征比较

L-FBF结构的内存需求是一个学习模型、一个FR-BF和一个V-FBF的内存需求的总和。用mw表示模型所需的内存，mb表示FR-BF中的神经元数量，mv表示V-FBF中的神经元数量，l表示V-FBF的神经元中的比特数。L-FBF结构的总内存需求（Ml）如下：
Ml = mw + mb + mvl
表2对比了L-FBF结构和单个FBF的内存需求。
表2 L-FBF和单个FBF的内存需求（KB）
3.2 搜索失败率
表3展示了单个FBF和基于不同模型的L-FBF结构之间的搜索失败率（SFRs）的比较。减少率是通过减少的搜索失败的次数（即单个FBF的搜索失败的次数减去L-FBF的搜索失败的次数）和单个FBF的搜索失败的次数来计算的。如图所示，与单一的FBF相比，所提出的LFBF结构减少了82.792%和83.894%的搜索失败。该模型并不会较大地受元素数量的影响，而且每个L-FBF中模型的内存需求相当小，与数据大小无关。因此，随着数据大小的增加，L-FBF比单一的FBF更有效。即使随机数据包含在负集中，因为负类数据既不存储在V-FBF中，也不存储在FR-BF中，所以L-FBF也会返回具有相同的假阳性概率的结果。
表4 单一FBF和基于不同模型的L-FBF之间搜索失败率的比较（%）
四．总结
论文提出了一种学习型功能Bloom过滤器结构，用学习的模型替换FBF的核心部分，以提高FBF的搜索性能。所提出的L-FBF由一个学习模型、假类结果Bloom过滤器（FR-BF）和一个验证功能Bloom过滤器（V-FBF）组成，以提供与FBF相同的语义保证。实验结果表明，与使用相同内存的FBF相比，L-FBF结构减少了82.792% 83.894%的搜索失败概率。此外，如果有一个更准确的模型，L-FBF的内存需求还会减少。
-End-
本文作者
孙莹莹
重庆大学计算机科学与技术专业大三在读学生，重庆大学START团队成员。
主要研究方向：时空数据管理

时空艺术团队（START，Spatio-Temporal Art）来自重庆大学时空实验室，旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

概率计算分类数据预测模型
文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论