1.一种支持元素级别删除操作的数据流基数估计方法,其特征在于,包括:响应于更新操作,更新虚拟桶存储的桶数据序列;其中,所述虚拟桶设置有多个,每个所述虚拟桶均包括守卫单元和多个常规单元,所述守卫单元用于记录最小采样值,所述常规单元用于存储指纹;
获取非空单元数量,根据所述非空单元数量和更新后的所述桶数据序列,计算每个所述虚拟桶的桶级基数,表示为:;其中,所述非空单元数量为所述虚拟桶中存储有所述指纹的所述常规单元的数量,为所述指纹的位宽,为当前的所述虚拟桶的所述最小采样值,为当前的所述虚拟桶的所述非空单元数量,为所述虚拟桶的所述常规单元的数量,,,为所述虚拟桶的数量;
将各个所述虚拟桶的所述桶级基数进行累加,计算数据流的全局数据基数。
2.根据权利要求1所述的支持元素级别删除操作的数据流基数估计方法,其特征在于:所述更新操作包括插入操作;
响应于所述插入操作,更新所述虚拟桶存储的所述桶数据序列,包括:根据桶索引哈希函数处理待插入数据元素,得到第一桶索引;其中,所述待插入数据元素为所述插入操作所要插入的数据元素;
根据所述第一桶索引,确认第一目标桶;其中,所述第一目标桶为所述第一桶索引对应的所述虚拟桶;
根据指纹哈希函数处理所述待插入数据元素,得到第一指纹;
判断所述第一指纹是否满足采样条件;其中,在满足所述采样条件的情况下,所述第一指纹未存储在第一常规单元中,且所述第一指纹小于第一目标值;所述第一常规单元属于所述第一目标桶,所述第一目标值为所述第一目标桶当前的所述最小采样值;
若所述第一指纹满足所述采样条件,则获取第二目标值,并判断所述第一指纹是否小于所述第二目标值;其中,所述第二目标值为所述第一目标桶当前的最大指纹值;
若所述第一指纹不小于所述第二目标值,则将所述第一目标值更新为所述第二目标值,并结束当前的所述插入操作;
若所述第一指纹不满足所述采样条件,则结束当前的所述插入操作。
3.根据权利要求2所述的支持元素级别删除操作的数据流基数估计方法,其特征在于,在所述第一指纹满足所述采样条件的情况下:若所述第一指纹小于所述第二目标值,则判断目标常规单元是否为空值;其中,所述目标常规单元为对应所述第二目标值的所述常规单元,所述空值为数据类型的最大值,在所述目标常规单元为所述空值的情况下,所述目标常规单元未存储所述指纹;
若所述目标常规单元为所述空值,则将所述第一指纹插入所述目标常规单元,并结束当前的所述插入操作;
若所述目标常规单元不为所述空值,则将所述第一目标值更新为所述第二目标值;在更新所述第一目标值后,将所述第二目标值更新为所述第一指纹,并结束当前的所述插入操作。
4.根据权利要求2或3所述的支持元素级别删除操作的数据流基数估计方法,其特征在于,在判断所述第一指纹是否满足采样条件之前,还包括对所述第一目标桶进行预处理;对所述第一目标桶进行预处理,包括:获取待插入附加属性;所述待插入附加属性为所述待插入数据元素的附加属性;
根据预设策略函数验证第二常规单元,确认所述第二常规单元是否存储过期指纹;其中,所述第二常规单元属于所述第一目标桶;所述过期指纹为未通过所述预设策略函数验证的指纹;
若所述第二常规单元存储有所述过期指纹,则将所述第二常规单元设置为空值,将过期附加属性更新为所述待插入附加属性,并结束当前的所述预处理;其中,在所述第二常规单元为所述空值的情况下,所述第二常规单元未存储所述指纹;所述过期附加属性为所述第二常规单元的附加属性;
若所述第二常规单元未存储所述过期指纹,则结束当前的所述预处理。
5.根据权利要求4所述的支持元素级别删除操作的数据流基数估计方法,其特征在于,在根据预设策略函数验证所述第一目标桶之前,还包括:判断所述待插入附加属性是否为空;
若所述待插入附加属性为空,则转至判断所述第一指纹是否满足采样条件;
若所述待插入附加属性不为空,则转至根据预设策略函数验证所述第一目标桶。
6.根据权利要求4所述的支持元素级别删除操作的数据流基数估计方法,其特征在于:所述待插入附加属性包括时间戳;
所述预设策略函数设置为时间策略验证函数,所述时间策略验证函数表示为:,
其中,的值为表示当前的所述第二常规单元的所述指纹通过验证,的值为表示当前的所述第二常规单元的所述指纹未通过验证;为当前的所述时间戳;为当前的所述第二常规单元存储的所述指纹,为历史时间戳,所述历史时间戳为当前的所述第二常规单元的所述时间戳;为预设时间窗口。
7.根据权利要求4所述的支持元素级别删除操作的数据流基数估计方法,其特征在于:所述待插入附加属性包括时间戳和空间区域;
所述预设策略函数设置为时空策略验证函数,所述时空策略验证函数表示为:,
其中,的值为表示当前的所述第二常规单元的所述指纹通过验证,的值为表示当前的所述第二常规单元的所述指纹未通过验证;为当前的所述时间戳;为当前的所述第二常规单元存储的所述指纹,为历史时间戳,所述历史时间戳为当前的所述第二常规单元的所述时间戳;为预设时间窗口;为历史空间区域,所述历史空间区域为当前的所述第二常规单元的所述空间区域;为预设空间区域。
8.根据权利要求1所述的支持元素级别删除操作的数据流基数估计方法,其特征在于:所述更新操作包括被动删除操作;
响应于所述被动删除操作,更新所述虚拟桶存储的所述桶数据序列,包括:根据桶索引哈希函数处理待删除数据元素,得到第二桶索引;其中,所述待删除数据元素为所述被动删除操作所要删除的数据元素;
根据所述第二桶索引,确认第二目标桶;其中,所述第二目标桶为所述第二桶索引对应的所述虚拟桶;
根据指纹哈希函数处理所述待删除数据元素,得到第二指纹;
判断所述第二指纹是否满足删除条件;其中,所述删除条件为所述第二指纹存储在第三常规单元中,所述第三常规单元属于所述第二目标桶;
若满足所述删除条件,则将所述第三常规单元设置为空值,并结束当前的所述被动删除操作;在所述第三常规单元为所述空值的情况下,所述第三常规单元未存储所述指纹;
若不满足所述删除条件,则结束当前的所述被动删除操作。
9.根据权利要求1所述的支持元素级别删除操作的数据流基数估计方法,其特征在于:将各个所述虚拟桶的所述桶级基数进行累加,计算数据流的全局数据基数,表示为:。
10.根据权利要求1所述的支持元素级别删除操作的数据流基数估计方法,其特征在于,在响应于更新操作之前,还包括:设置所述虚拟桶的数量,以及每个所述虚拟桶的所述常规单元的数量;其中,每个所述虚拟桶的所述常规单元的数量相等;
将每个所述常规单元设置为空值;其中,所述空值为数据类型的最大值;
将每个所述守卫单元的值设置为初始采样值;其中,所述初始采样值为数据类型的最大值;
定义桶索引哈希函数和指纹哈希函数;其中,所述桶索引哈希函数用于获取数据元素对应的桶索引,所述指纹哈希函数用于获取数据元素对应的指纹。