重庆大学微电子与通信工程学院 张家铭

本文提出了一种扩展PIE算法，使用新型的数据结构Dynamic Cuckoo Filter替代PIE算法中的空时布隆过滤器，用Raptor码编码对象的ID信息，大幅降低对象存储所需的空间，并在后续过程解码识别持续热点的原始ID。识别阶段，扩展PIE算法利用一个Cuckoo Filter加速热点查询过程，将PIE算法识别阶段的平方时间复杂度降低为线性复杂度。实验结果证明，扩展PIE算法的查询时间复杂度和空间效率均优于PIE算法。

1 研究背景

作为流处理挖掘技术一个重要问题，高频热点挖掘技术获得了许多研究人员的关注，取得了众多的研究成果。

作为高频热点问题的广义扩展，持续热点识别是流处理挖掘的一个新问题。在一个短周期内，不同于高频热点，持续热点并不比其他对象有更大的出现频率，却会在长周期内连续出现。持续热点挖掘技术可以应用在一系列的应用上，如网络安全中，持续热点挖掘技术可以检测稳定的DDoS攻击，即攻击者并不在短时间内采用大流量攻击，而是在很长的时间内用数量较少的机器保持稳定的攻击。

2 PIE算法

2.1 记录阶段

在记录阶段，PIE在给定的观察周期，记录下所在观察节点的所观察到的ID信息。在每个观察周期的开始阶段，PIE在SRAM中初始化一个STBF，并在该周期记录完毕后将STBF存入固定存储器中。STBF初始化过程中，每个元胞对应的三个域(标志位域，Raptor码域，信息指纹域)都清零。在观察周期i观察到对象e，PIE有三个处理步骤：

一、计算出对应的ID的r位Raptor码和p位信息指纹。……