(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211184924.2 (22)申请日 2022.09.27 (71)申请人 青海师范大学 地址 810016 青海省西宁市城西区五四西 路38号 (72)发明人 谢平　华文镝　 (74)专利代理 机构 成都东恒知盛知识产权代理 事务所 (特殊普通合伙) 51304 专利代理师 李英 (51)Int.Cl. G06F 16/2453(2019.01) G06F 16/22(2019.01) G06F 16/2458(2019.01) (54)发明名称 一种基于布谷鸟过滤器的近似成员查询优 化方法 (57)摘要 本发明公开了一种基于布谷鸟过滤器的近 似成员查询优化方法， 首先是要根据存储集合的 大小使用“Balls in Bins”模型计算应 该对过滤 器分成几个子过滤器， 每个元素的所有操作都在 其所在的子过滤器内。 对于后续元素插入无限循 环情况的判定也在此时依据集合元素个数进行 计算。 在元素插入时， 首先利用基于位移操作的 随即映射方式计算元素的两个候选桶， 随后使用 “积极主动 ”的插入策略将元素第一个候选桶的 最后一个槽预留给其他元素进行重定位。 重定位 时从后向前检查同种的空槽， 减少检查槽的个 数。 同时， 在元素重定位的过程中， 使用计算所得 的动态阈值来对 无限循环问题进行判定。 本发明 具有更高效的空间使用效率、 更优良的元素插入 操作和更 快的无限循环判定 。 权利要求书2页 说明书5页 附图2页 CN 115510092 A 2022.12.23 CN 115510092 A 1.一种基于布谷鸟过 滤器的近似成员查询优化方法， 其特 征在于， 包括如下步骤： 步骤一、 根据集 合的元素数量计算无限循环阈值； 步骤二、 对布谷鸟过 滤器进行分块， 划分为各子过 滤器； 步骤三、 在用户发起请求之前， 将集合中的元素插入到过滤器中， 每个元素随机映射到 一个子过滤器中的两个映射候选桶中， 所有元素 的映射候选桶都受 限于一个子过滤器中， 使用基于位移操作的随机映射方式为元 素计算其两个候选桶的索引位置； 步骤四、 使用 “积极主动 ”的元素插入策略把元 素插入到映射桶中； 步骤五、 对于使用 “积极主动 ”插入策略未能插入成功的元素， 进入元素重定位阶段， 在 动态重定位阈值的检测下， 从后向前探测每一个重定位桶中是否存在 “空槽”； 当元素重定 位的次数达 到重定位阈值时， 则认为该 元素陷入了无限循环中， 元 素插入失败； 步骤六、 插入结束后， 接受外部的用户请求， 用户的外部请求可以直接在内存中的过滤 器中完成， 无需进入真正的集 合中去操作。 2.根据权利要求1所述的基于布谷鸟过滤器的近似成员查询优化方法， 其特征在于： 在 步骤二中， 采用 “Balls in Bins”模型对布谷鸟过滤器进行分块， 每个分块大小相同， 桶 数 为2m； 分块的策略是让每个块中的最大元素个数在小于设定 的空间效率的情况下， 让块的 大小最小， 尽可能多的对过 滤器进行分块。 3.根据权利要求1所述的基于布谷鸟过滤器的近似成员查询优化方法， 其特征在于： 所 述“积极主动 ”的元素插入策略具体是： 设每个映射桶共有b个槽， 插入元素时， 对于第一个候选桶仅 检查前b‑1个槽是否有空， 如果存在空则插入元素， 如果没有空也不再检查最后一个槽， 将其留给其他元素重定位时 使用， 进而检查第二个候选桶； 对于第二个候选桶则检查 其中所有的槽是否有空， 如果有空就插 入元素。 4.根据权利要求1所述的基于布谷鸟过滤器的近似成员查询优化方法， 其特征在于： 在 步骤五中， 元素重定位具体包括： 随机选择第二个候选桶中的一个元素， 将其踢 出槽以插入 这个待插入元素， 被踢出的元素递归地寻找其两个候选桶中另外一个是否存在空槽可以插 入， 查找的顺序为从后向前， 完成元 素重定位。 5.根据权利要求1所述的基于布谷鸟过滤器的近似成员查询优化方法， 其特征在于： 在 步骤五中， 动态重 定位阈值是根据集 合元素的数量 来计算的， 具体如下： 其中， d表示每个元素的候选桶个数， b表示每个桶中槽的个数， C则表示过滤器整体中 分块的个数。 6.根据权利要求1所述的基于布谷鸟过滤器的近似成员查询优化方法， 其特征在于： 步 骤六中， 外 部的用户请求包括元 素查询请求、 元 素插入请求和元 素删除请求。 7.根据权利要求6所述的基于布谷鸟过 滤器的近似成员查询优化方法， 其特 征在于： 对于元素查询请求， 使用插入时相同的映射函数， 将元素映射到两个桶中， 只需检查对 应桶中的所有元 素是否有待查找的元 素即可； 对于元素插入请求， 使用 “积极主动 ”的元素插入策略和元素重定位来进行插入， 如果 在重定位时达 到了重定位阈值时， 则说明不可以再插 入元素， 停止插 入；权　利　要　求　书 1/2 页 2 CN 115510092 A 2对于元素删除请求， 首先发起元素查询请求， 找到该元素后， 则先在集合中删除， 再删 除过滤器中的对应信息 。权　利　要　求　书 2/2 页 3 CN 115510092 A 3