本申请具体公开了一种低开销的突发数据流检测算法,本申请利用所构建小流过滤器和突发流检测表对输入的数据流进行过滤和识别,进而输出真正的突发流,其通过设置时间周期不断过滤低频率流以识别出潜在突发流,提高了后续突发流的检测精度;同时利用突发流检测表对潜在突发流进行跟踪,基于每个潜在突发流在两个相邻时间周期内的频率以及突增周期,进而识别出该潜在突发流是否为真正的突发流;而且,还采用突发周期与数据流频率概率的替换策略剔除突发性较低的数据流,以便于存储更具有可能性的潜在突发流,进一步降低了内存消耗。因此,本申请所提供的突发数据流检测算法具有高精确性、低开销和高吞吐量的特点。
背景技术
在早期的突发流识别方案中,将突发仅定义为流频率突然增加而忽略了突然减少的情况,然而在某些场景下,关注流频率的突然减少同样很重要。目前,BurstSketch是首个在专注于在高速数据流中检测突发流的Sketch算法,并取得了不错的性能。但是,此方案使用的计数器为了能记录每条流的ID和频率需要分配较大的内存,导致存储开销过大,在存储时由于哈希冲突的影响导致一些可疑的突发流被踢出去,降低了识别的准确性。因此,现有实时检测突发流的方案并不能同时实现高精度、低内存开销和高吞吐量。
实现思路