本技术涉及计算机技术领域,具体提供了一种支持元素级别删除操作的数据流基数估计方法,包括响应于更新操作,更新虚拟桶存储的桶数据序列;其中,所述虚拟桶设置有多个,每个所述虚拟桶均包括守卫单元和多个常规单元,所述守卫单元用于记录最小采样值,所述常规单元用于存储指纹;获取非空单元数量,根据所述非空单元数量和更新后的所述桶数据序列,计算每个所述虚拟桶的桶级基数;其中,所述非空单元数量为所述虚拟桶中存储有所述指纹的所述常规单元的数量;将各个所述虚拟桶的所述桶级基数进行累加,计算数据流的全局数据基数。本发明基于虚拟桶对目标数据动态更新并计算数据流的全局数据基数,内存利用率高,计算快而准。
背景技术
数据流基数指的是数据流中不同的数据元素的数量。在数据库管理、网络测量以及安全系统中,数据流基数估计是一个基础性任务,其能够为数据处理和资源管理提供关键支持,且数据流基数估计广泛应用于实时数据分析。示例性的,数据库系统可以通过监控不同查询、事务以及列值的数量,以便动态调整索引策略和资源分配,从而有效应对高并发的动态负载。在网络流量监测中,基数估算则用于跟踪IP地址和连接的唯一性,以识别异常行为。在网络安全领域,基数估算技术被用于实时分析入侵检测系统(简称IDS)中的数据包,及时检测异常活动,确保系统稳定性。
传统的数据流基数估计方法包括PCSA、LogLog和HyperLogLog等。尽管这些传统的数据流基数估计方法在插入操作和内存效率方面展示了极大优势,但由于无法应对数据元素的删除需求,导致了这些方法在动态应用场景中的适应性受限。也有基于哈希表的“right-to-be-forgotten”数据流模型(简称RFDS),能够支持对特定数据元素的手动删除操作,但RFDS处理速度在复杂度和内存利用率方面表现出明显的不足。
实现思路