欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2024102938706
申请人: 苏州大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种时空高效的并行近似成员查询方法,其特征在于,包括:

根据用户需求对过滤器进行初始化,具体包括:初始化过滤器的子过滤器数量;初始化每个子过滤器;每个子过滤器包含多个存储桶,每个存储桶包含多个存储槽;每个子过滤器为每个数据元素提供一个候选存储桶;将子过滤器对应分配到流水线阶段;每个子过滤器对应一个流水线阶段以进行流水线并行操作;

获取待操作的数据集合;所述操作包括插入操作、查找操作和删除操作;

将所述数据集合中的数据元素分为多个不相交的子数据集合,每个子数据集合分别对应一个流水线阶段;

每个流水线阶段依次不断地处理等待操作的数据元素;

当每个流水线阶段对所述数据元素的操作完成,判断是否返回操作结果;

若是,则返回操作成功的结果,或在操作失败且已遍历完全部流水线阶段或达到预设踢出操作次数时返回操作失败的结果;

若否,则所述数据元素在当前流水线阶段操作失败,进入下一个流水线阶段进行操作;

其中,进行所述插入操作的具体步骤包括:

获取待插入数据元素,并计算得到所述待插入数据元素的指纹;

结合所述待插入数据元素的指纹、当前流水线阶段的索引、前一个流水线阶段的索引,计算得到所述待插入数据元素在当前流水线阶段中候选存储桶的索引;

判断所述候选存储桶中是否有空存储槽;若有,则将所述待插入数据元素的指纹存入一个空存储槽中,返回插入成功的结果;若没有,则随机选择所述候选存储桶中的一个存储槽进行踢出操作;

判断是否达到预设踢出操作次数;若是,则放弃插入并返回插入失败的结果;若否,则将所述待插入数据元素的指纹进入下一个流水线阶段继续进行插入操作,直至出现空存储槽或达到最大踢出操作次数。

2.根据权利要求1所述的时空高效的并行近似成员查询方法,其特征在于,在每个流水线阶段依次不断地处理等待操作的数据元素中,所述数据元素的来源包括:被分配到当前流水线阶段等待首次操作的数据元素,或前一个流水线阶段操作失败的数据元素。

3.根据权利要求1所述的时空高效的并行近似成员查询方法,其特征在于,所述踢出操作包括:从所述候选存储桶中随机选择一个存储槽,交换所述存储槽和所述待插入数据元素的指纹的值。

4.根据权利要求1所述的时空高效的并行近似成员查询方法,其特征在于,在对数据元素进行操作的过程中,还通过流水线哈希法计算得到候选存储桶的索引,具体包括:通过当前流水线阶段的候选存储桶索引顺序计算下一个流水线阶段的候选存储桶索引;

基于最后一个流水线阶段的候选存储桶索引计算初始流水线阶段的候选存储桶索引。

5.一种时空高效的并行近似成员查询方法,其特征在于,包括:

根据用户需求对过滤器进行初始化,具体包括:初始化过滤器的子过滤器数量;初始化每个子过滤器;每个子过滤器包含多个存储桶,每个存储桶包含多个存储槽;每个子过滤器为每个数据元素提供一个候选存储桶;将子过滤器对应分配到流水线阶段;每个子过滤器对应一个流水线阶段以进行流水线并行操作;

获取待操作的数据集合;所述操作包括插入操作、查找操作和删除操作;

将所述数据集合中的数据元素分为多个不相交的子数据集合,每个子数据集合分别对应一个流水线阶段;

每个流水线阶段依次不断地处理等待操作的数据元素;

当每个流水线阶段对所述数据元素的操作完成,判断是否返回操作结果;

若是,则返回操作成功的结果,或在操作失败且已遍历完全部流水线阶段或达到预设踢出操作次数时返回操作失败的结果;

若否,则所述数据元素在当前流水线阶段操作失败,进入下一个流水线阶段进行操作;

其中,进行所述查找操作的具体步骤包括:

获取待查找数据元素,并计算得到所述待查找数据元素的指纹;

结合所述待查找数据元素的指纹、当前流水线阶段的索引、前一个流水线阶段的索引,计算得到所述待查找数据元素在当前流水线阶段中候选存储桶的索引;

判断所述当前流水线阶段的候选存储桶中是否有存储槽的值等于所述待查找数据元素的指纹值;若是,则返回查找成功的结果;

若否,则判断是否已经查找完所有的流水线阶段;若已经查找完所有的流水线阶段,则返回查找失败的结果;

若没有查找完所有的流水线阶段,则进入下一个流水线阶段继续进行查找操作。

6.一种时空高效的并行近似成员查询方法,其特征在于,包括:

根据用户需求对过滤器进行初始化,具体包括:初始化过滤器的子过滤器数量;初始化每个子过滤器;每个子过滤器包含多个存储桶,每个存储桶包含多个存储槽;每个子过滤器为每个数据元素提供一个候选存储桶;将子过滤器对应分配到流水线阶段;每个子过滤器对应一个流水线阶段以进行流水线并行操作;

获取待操作的数据集合;所述操作包括插入操作、查找操作和删除操作;

将所述数据集合中的数据元素分为多个不相交的子数据集合,每个子数据集合分别对应一个流水线阶段;

每个流水线阶段依次不断地处理等待操作的数据元素;

当每个流水线阶段对所述数据元素的操作完成,判断是否返回操作结果;

若是,则返回操作成功的结果,或在操作失败且已遍历完全部流水线阶段或达到预设踢出操作次数时返回操作失败的结果;

若否,则所述数据元素在当前流水线阶段操作失败,进入下一个流水线阶段进行操作;

其中,进行所述删除操作的具体步骤包括:

获取待删除数据元素,并计算得到所述待删除数据元素的指纹;

结合所述待删除数据元素的指纹、当前流水线阶段的索引、前一个流水线阶段的索引,计算得到所述待删除数据元素在当前流水线阶段中候选存储桶的索引;

判断所述候选存储桶中是否有存储槽的值等于所述待删除数据元素的指纹值;若是,则执行删除操作,将对应的存储槽置为空,返回删除成功的结果;

若否,则判断是否已经查找完所有的流水线阶段;若已经查找完所有的流水线阶段,则代表过滤器中没有存储所述待删除数据元素,返回删除失败的结果;

若没有查找完所有的流水线阶段,则进入下一个流水线阶段继续进行删除操作。

7.一种时空高效的并行近似成员查询系统,应用于上述权利要求1-6任一项所述的时空高效的并行近似成员查询方法,其特征在于,包括初始化模块、流水线哈希模块和流水线并行模块,其中:所述初始化模块用于,根据用户需求对过滤器进行初始化;

所述流水线哈希模块用于,通过流水线哈希法计算得到流水线阶段的候选存储桶的索引;

所述流水线并行模块用于,获取待操作的数据集合;将所述数据集合中的数据元素分为多个不相交的子数据集合,每个子数据集合分别对应一个流水线阶段;每个流水线阶段依次不断地处理等待操作的数据元素;当每个流水线阶段对所述数据元素的操作完成,判断是否返回操作结果;若是,则返回操作成功的结果,或在操作失败且已遍历完全部流水线阶段或达到预设踢出操作次数时返回操作失败的结果;若否,则所述数据元素在当前流水线阶段操作失败,进入下一个流水线阶段进行操作;

其中,所述流水线并行模块还包括插入操作模块、查找操作模块和删除操作模块,其中:所述插入操作模块用于,获取待插入数据元素,并计算得到所述待插入数据元素的指纹;结合所述待插入数据元素的指纹、当前流水线阶段的索引、前一个流水线阶段的索引,计算得到所述待插入数据元素在当前流水线阶段中候选存储桶的索引;判断所述候选存储桶中是否有空存储槽;若有,则将所述待插入数据元素的指纹存入一个空存储槽中,返回插入成功的结果;若没有,则随机选择所述候选存储桶中的一个存储槽进行踢出操作;判断是否达到预设踢出操作次数;若是,则放弃插入并返回插入失败的结果;若否,则将所述待插入数据元素的指纹进入下一个流水线阶段继续进行插入操作,直至出现空存储槽或达到最大踢出操作次数。

8.根据权利要求7所述的时空高效的并行近似成员查询系统,其特征在于,所述查找操作模块用于,获取待查找数据元素,并计算得到所述待查找数据元素的指纹;结合所述待查找数据元素的指纹、当前流水线阶段的索引、前一个流水线阶段的索引,计算得到所述待查找数据元素在当前流水线阶段中候选存储桶的索引;判断所述当前流水线阶段的候选存储桶中是否有存储槽的值等于所述待查找数据元素的指纹值;若是,则返回查找成功的结果;若否,则判断是否已经查找完所有的流水线阶段;若已经查找完所有的流水线阶段,则返回查找失败的结果;若没有查找完所有的流水线阶段,则进入下一个流水线阶段继续进行查找操作;

所述删除操作模块用于,获取待删除数据元素,并计算得到所述待删除数据元素的指纹;结合所述待删除数据元素的指纹、当前流水线阶段的索引、前一个流水线阶段的索引,计算得到所述待删除数据元素在当前流水线阶段中候选存储桶的索引;判断所述候选存储桶中是否有存储槽的值等于所述待删除数据元素的指纹值;若是,则执行删除操作,将对应的存储槽置为空,返回删除成功的结果;若否,则判断是否已经查找完所有的流水线阶段;若已经查找完所有的流水线阶段,则代表过滤器中没有存储所述待删除数据元素,并返回删除失败的结果;若没有查找完所有的流水线阶段,则进入下一个流水线阶段继续进行删除操作。