1.一种可动态调整大小的近似成员查询方法,其特征在于,包括:获取待操作数据;所述待操作数据的操作包括插入操作、查询操作、删除操作和段级别扩展操作;
对近似成员查询数据结构进行初始化;
将所述待操作数据输入至初始化完成的近似成员查询数据结构,并对所述待操作数据进行目标操作;
对近似成员查询数据结构进行初始化包括:
构建多个段;
构建一个查找表;所述查找表用于完成数据元素到段的映射,以使所述数据元素可以在对应的段中完成相关操作;
其中,对所述查找表进行初始化,将所述查找表平均划分为多份;
所述待操作数据的插入操作步骤包括:
获取待插入数据元素的指纹,并通过所述查找表将所述待插入数据元素映射到对应的候选段;
判断所述候选段是否可以插入所述待插入数据元素;若是,则在所述候选段中找到第一候选桶和第二候选桶;若否,则对所述近似成员查询数据结构进行段级别扩展;
判断所述第一候选桶和所述第二候选桶中是否存在一个空槽;若是,则在空槽中存储所述待插入数据元素的指纹;若否,则启动驱逐操作;
其中,对所述近似成员查询数据结构进行段级别扩展,包括:添加一个扩展段;
更改所述查找表到段号之间的映射关系;
通过遍历所述候选段中存储的指纹,完成所述候选段与所述扩展段之间数据元素的移动。
2.根据权利要求1所述的可动态调整大小的近似成员查询方法,其特征在于,所述驱逐操作为:将所述第一候选桶或所述第二候选桶中被驱逐的指纹重新定位到其中的另一个候选桶中,直至找到一个空槽,或驱逐的指纹数量超出预设阈值。
3.根据权利要求1所述的可动态调整大小的近似成员查询方法,其特征在于,通过遍历所述候选段中存储的指纹,完成所述候选段与所述扩展段之间数据元素的移动,包括:将所述查找表中的条目进行区分;所述查找表中有多个条目指向候选段,将多个条目平均分为第一部分和第二部分,所述第一部分的条目指向所述候选段,所述第二部分的条目指向所述扩展段;
遍历所述候选段中存储的指纹,判断每个指纹是否由所述第二部分的条目映射到所述候选段,并将由所述第二部分的条目映射到所述候选段中的指纹移动到所述扩展段中。
4.根据权利要求1所述的可动态调整大小的近似成员查询方法,其特征在于,所述待操作数据的查询操作步骤包括:获取待查询数据元素的指纹,并通过查找表将所述待查询数据元素映射到对应的候选段;
在所述候选段中查找得到两个候选桶;
在两个候选桶中查找是否有一个槽中存储所述待查询数据元素的指纹;若是,则报告所述待查询数据元素属于当前数据集合;若否,则报告所述待查询数据元素不属于当前数据集合。
5.根据权利要求1所述的可动态调整大小的近似成员查询方法,其特征在于,所述待操作数据的删除操作步骤包括:获取待删除数据元素的指纹,并通过查找表将所述待删除数据元素映射到对应的候选段;
在所述候选段中查找得到两个候选桶;
在两个候选桶中查找存储有所述待删除数据元素的指纹的槽;
对存储有所述待删除数据元素的指纹的槽进行清空操作。
6.一种可动态调整大小的近似成员查询系统,应用于上述权利要求1-5任一项所述的可动态调整大小的近似成员查询方法,其特征在于,包括初始化模块、元素插入模块、元素查询模块、元素删除模块,其中:所述初始化模块用于,对近似成员查询数据结构进行初始化;
所述元素插入模块用于,获取待插入数据元素的指纹,并通过查找表将所述待插入数据元素映射到对应的候选段;判断所述候选段是否可以插入所述待插入数据元素;若是,则在所述候选段中找到第一候选桶和第二候选桶;若否,则对所述近似成员查询数据结构进行段级别扩展;判断所述第一候选桶和所述第二候选桶中是否存在一个空槽;若是,则在空槽中存储所述待插入数据元素的指纹;若否,则启动驱逐操作;
所述元素查询模块用于,获取待查询数据元素的指纹,并通过查找表将所述待查询数据元素映射到对应的候选段;在所述候选段中查找得到两个候选桶;在两个候选桶中查找是否有一个槽中存储所述待查询数据元素的指纹;若是,则报告所述待查询数据元素属于当前数据集合;若否,则报告所述待查询数据元素不属于当前数据集合;
所述元素删除模块用于,获取待删除数据元素的指纹,并通过查找表将所述待删除数据元素映射到对应的候选段;在所述候选段中查找得到两个候选桶;在两个候选桶中查找存储有所述待删除数据元素的指纹的槽;对存储有所述待删除数据元素的指纹的槽进行清空操作。
7.根据权利要求6所述的可动态调整大小的近似成员查询系统,其特征在于,还包括段级别扩展模块用于,添加一个扩展段;更改所述查找表到段号之间的映射关系;通过遍历所述候选段中存储的指纹,完成所述候选段与所述扩展段之间数据元素的移动。