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

摘要:

权利要求书:

1.一种面向动态k-mer数据集的近似成员查询索引生成方法,其特征在于,包括:根据基数估计算法对需要存储的目标数据集的元素基数进行确定;

根据所述元素基数选择需要存储的第一层级的目标第一单元;第一层级的多个第一单元的布隆过滤器数量不同,第一单元的布隆过滤器的容量均相同,布隆过滤器用于存储目标数据集中对应的元素,第一单元可存储的元素基数不小于对应的数据集的元素基数;

通过所述目标第一单元的分组函数,根据所述目标数据集的目标元素,生成所述目标元素的第二层级的第二单元索引,将所述目标元素划分到所述第二单元索引对应的目标第二单元中;第一单元包括多个第二单元,第一单元中存储的每个数据集的第二单元的数量,与对应的数据集需要的布隆过滤器数量相同;

将所述目标元素存储到所述目标第二单元中的第三层级的目标第三单元中,并分配给所述目标数据集的布隆过滤器;第二单元包括多个大小固定的第三单元,第三单元的组织形式为交错布隆过滤器,第三单元在查询元素时根据交错布隆过滤器一次性读取不同布隆过滤器的同一位;

进行第一k-mer数据集插入时,先根据第一k-mer数据集的元素基数,确定对应的插入第一单元;在确定第一单元之后,将第一单元中的第三单元的组织形式,从交错布隆过滤器转换为布隆过滤器矩阵;在插入之后,将插入第一单元的第三单元的组织形式从布隆过滤器矩阵转换为交错布隆过滤器;

进行第二k-mer数据集删除时,先查询到第二k-mer数据集的所属的第一单元;在确定第一单元之后,将第一单元中的第三单元的组织形式,从交错布隆过滤器转换为布隆过滤器矩阵;在删除之后,将插入第一单元的第三单元的组织形式从布隆过滤器矩阵转换为交错布隆过滤器。

2.根据权利要求1所述的方法,其特征在于,根据所述基数选择需要存储的第一层级的目标第一单元,包括:目标数据集的元素基数,与第一单元可存储的元素基数进行比较;

在所述目标数据集的元素基数,小于或等于比较第一单元可存储的元素基数,且大于上一第一单元可存储的元素基数的情况下,将所述比较第一单元作为所述目标第一单元;

其中,所述比较第一单元为多个第一单元之一,所述上一第一单元为比所述比较第一单元的布隆过滤器数量少预设差值的第一单元。

3.根据权利要求1所述的方法,其特征在于,将所述目标元素存储到所述目标第二单元中的第三层级的目标第三单元中,并分配给所述目标数据集的布隆过滤器,包括:将所述目标元素存储到所述目标第二单元中的第三层级的目标第三单元中;

使用所述目标第三单元的多个独立的哈希函数,对所述目标元素进行哈希处理,并映射到对应的布隆过滤器中对应位置,将所述对应位置设置为1。

4.根据权利要求1所述的方法,其特征在于,所述方法还包括:

接收需要插入的第一数据集;

根据所述第一数据集的元素基数,确定对应的插入第一单元;

将所述插入第一单元的第三单元的组织形式从交错布隆过滤器,转换为布隆过滤器矩阵;

在所述插入第一单元中查找对应的插入位置,其中,所述插入位置是通过布隆过滤器查找到的;

将所述第一数据集插入到所述插入位置,并为所述第一数据集分配对应的布隆过滤器;

将所述插入第一单元的第三单元的组织形式从布隆过滤器矩阵转换为交错布隆过滤器。

5.根据权利要求1所述的方法,其特征在于,所述方法还包括:

接收需要删除的第二数据集;

查询所述第二数据集对应的所属第一单元;

将所述所属第一单元的第三单元的组织形式从交错布隆过滤器,转换为布隆过滤器矩阵;

在所述第二数据集的元素集合为第三单元的部分元素集合的情况下,将所述第二数据集对应的布隆过滤器删除,保留空位;

在所述第二数据集的元素集合为第三单元的全部元素集合的情况下,将所述第二数据集对应的布隆过滤器删除,并释放所述第三单元的空间资源;

将所述所属第一单元的第三单元的组织形式从布隆过滤器矩阵转换为交错布隆过滤器。

6.一种面向动态k-mer数据集的近似成员查询方法,其特征在于,根据权利要求1至5中任一项所述的面向动态k-mer数据集的近似成员查询索引生成方法,生成的索引进行查询,包括:通过第一层级的第一单元的分组函数,以及需要查询的目标元素,生成所述目标元素在所述第一单元中第二层级的第二单元索引,以标识所述目标元素所在的目标第二单元,其中,所述目标元素以多个层级的方式逐级索引,在存储进第二层级时,利用所属的第一单元的所述分组函数生成对应的第二单元索引,并存储到所述第二单元索引对应的目标第二单元中;

在所述第一单元存在所述目标第二单元的情况下,确定所述目标元素存储在所述第一单元的所述目标第二单元中;

获取所述目标第二单元中第三层级的第三单元的交错布隆过滤器,根据所述交错布隆过滤器,获取多个哈希索引,其中,所述第三单元为所属的第二单元的组成部分,所述目标元素在存储进第三单元时,会分配给所属的目标数据集的布隆过滤器,所述第三单元的组织形式为交错布隆过滤器,所述哈希索引的位数与所述目标第二单元的布隆过滤器的数量相同,所述布隆过滤器与不同的数据集相对应;

根据所述哈希索引查询所述目标元素所属的目标数据集。

7.根据权利要求6所述的方法,其特征在于,根据所述哈希索引查询所述目标元素所属的目标数据集,包括:对多个所述哈希索引进行按位与操作,得到目标索引,其中,所述哈希索引为不同布隆过滤器的同一位的数据,哈希索引为同一哈希函数对不同数据集的元素的映射,所述哈希索引的不同位表示不同布隆过滤器的数值,所述数值表征所述布隆过滤器是否存在所述目标元素;

根据所述目标索引确定所述目标元素所属的目标数据集。

8.根据权利要求6所述的方法,其特征在于,在根据所述哈希索引查询所述目标元素所属的目标数据集之后,所述方法还包括:将所述目标数据集存储在输出列表中;

继续查询其他的第一单元中是否存在所述目标元素的索引;

在第一单元存在所述目标元素的索引的情况下,获取所属的目标数据集,并存储在输出列表中;

在所有的第一单元完成遍历的情况下,将所述输出列表输出。

9.根据权利要求1至8中任一项所述的方法,其特征在于,所述第一层级的第一单元为段单元,所述段单元包括多个布隆过滤器,每个所述段单元的布隆过滤器的容量均相同,一个布隆过滤器对应记录一个数据集中对应的元素,所述段单元可存储的数据集的元素基数大于等于需要存储的数据集的元素基数;

所述第二层级的第二单元为组单元,所述段单元中存储的每个数据集的所述组单元的数量,与对应的数据集需要的布隆过滤器数量相同;

所述第三层级的第三单元为块单元,所述块单元为数据大小固定的数据块,为所述组单元的组成单元,以交错布隆过滤器的组织形式存储不同元素的,所述块单元在查询元素时,根据交错布隆过滤器一次性读取不同布隆过滤器中与所述查询元素对应的位置的所有数据。

10.一种面向动态k-mer数据集的近似成员查询系统,包括:处理器,以及存储程序的存储器,其特征在于,所述程序包括指令,所述指令在由所述处理器执行时使所述处理器执行根据权利要求1至8中任一项所述的方法。