(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111479990.8 (22)申请日 2021.12.0 6 (71)申请人 北京大学 地址 100871 北京市海淀区颐和园路5号北 京大学 (72)发明人 杨仝　樊卓宸　 (74)专利代理 机构 北京君尚知识产权代理有限 公司 11200 专利代理师 邱晓锋 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/245(2019.01) G06N 20/00(2019.01) (54)发明名称 一种实时数据流查找周期性元素的方法和 装置 (57)摘要 本发明涉及一种实时数据流查找周期性元 素的方法和装置。 该方法建立基于Sketch的紧凑 数据结构为PeriodicSketch， 其包括两部分： Cover‑Min sketch和GSU  sketch； 使用Cover ‑ Min sketch记录和报告传入元素的时间间隔， 使 用GSU sketch记 录和报告top‑K最有潜力的周期 性 元 素 。本发 明 通 过 使 用紧 凑 数 据结 构 PeriodicSketch， 只需要极小的内存消耗， 就可 以以实时在高速的数据流中很准确地查找出所 有的周期性元素， 然后用户可根据自己的需求去 挑选出对应的时间间隔的元素， 可以用于Cache 预取、 检测高级持续性威胁、 流量预测/分类、 金 融交易和用户购买等领域。 权利要求书2页 说明书6页 附图2页 CN 115525643 A 2022.12.27 CN 115525643 A 1.一种实时数据流 查找周期性元 素的方法， 其特 征在于， 包括以下步骤： 建立基于Sketch的紧凑数据结构， 其包括两部分， 第一部分数据结构是Cover ‑Min  sketch， 第二部分数据结构是GSU  sketch； 利用Cover ‑Min sketch记录和报告传入元素的时间间隔， 然后将元素及其时间间隔组 合形成一个新元 素并插入GSU sketch中， 利用GSU  sketch记录和报告top ‑K的周期性元 素。 2.根据权利要求1所述的方法， 其特征在于， 所述Cover ‑Min sketch共有d个数组， 每个 数组由w个桶组成， 每个数组有一个对应的哈希函数， 共有d个相互独立的哈希 函数； 每个桶 有两个单元格， 分别记录元素e的ID和时间戳t； 所述GSU  sketch由u个桶组成， 并与一个哈 希函数h(.)相关联； 每个桶都有p个单元格， 每个单元格存储一个新元素<ID,V>和它的频数 f， 频数f是时间 间隔V的出现次数。 3.根据权利要求2所述的方法， 其特征在于， 所述Cover ‑Min sketch中元素的插入操作 包括： 当输入一个即将到来的元素及其时间戳时， 计算关联的d个哈希函数， 并映射到每个 哈希表的其中一个桶里， 总共被映射到d个桶， 然后将 每个映射的桶中的时间戳重写为当前 时间。 4.根据权利要求3所述的方法， 其特征在于， 所述Cover ‑Min sketch中元素的报告操作 包括： 对于当前元素及其时间戳， 计算关联的d个哈希函数， 从d个桶中提取其中的d个时间 戳； 用当前时间戳t减上述d个时间戳中最小的时间戳min_t， 得到当前的时间间隔V， 即V＝ t‑min_t， 并和该 元素一起报告。 5.根据权利要求4所述的方法， 其特征在于， 所述GSU  sketch中新元素的插入操作包 括： 对于传入的元素， 首先查询Cover ‑Min sketch得到的时间间隔V， 然后将元素的ID和它 的时间间隔V组合起来形成一个新元素<ID,V>， 然后通过哈希函数h(.)将该新元素映射到 其中一个桶中， 该桶设为桶j； 新元 素的插入有两种情况： 其一， 桶j的有单 元格已经存有这个新元 素， 在这种情况 下， 将频数f直接增 加1； 其二， 新元素不在桶j中， 分为两个子情况： 1)如果桶j未满， 直接将新元素插入桶j的任 意一个空单元格中， 并设置其频数为f＝ 1； 2)如果桶j已满， 尝试通过替换策略来替换桶 j里 的频数最小的元素， 即用一个替换概率P替换桶j里的频数最小的元素， 以确保在哈希表中 的元素越来越接 近真正的周期性元 素。 6.根据权利要求5所述的方法， 其特征在于， 所述替换概率P的表达式为： P＝1/(2 ×fm‑ tf+1)， 其中tf是替换失败的次数， fm是桶j里的频 数最小的元 素的频数。 7.根据权利要求1所述的方法， 其特征在于， 所述GSU  sketch中新元素的报告操作包 括： 直接遍历GSU  sketch的桶， 并返回具有top ‑K最大频数的新元 素。 8.一种采用权利要求1～7中任一权利要求所述方法的实时数据流查找周期性元素的 装置， 其特 征在于， 包括： Cover‑Min sketch模块， 用于记录和报告传入元素的时间间隔， 然后将元素及其时间 间隔组合 起来形成一个新元 素并插入GSU sketch模块中； GSU sketch模块， 用于记录和报告top ‑K的周期性元 素。 9.一种电子装置， 其特征在于， 包括存储器和 处理器， 所述存储器存储计算机程序， 所 述计算机程序被配置为由所述处理器执行， 所述计算机程序包括用于执行权利要求 1～7中 任一权利要求所述方法的指令 。权　利　要　求　书 1/2 页 2 CN 115525643 A 210.一种计算机可读存储介质， 其特征在于， 所述计算机可读存储介质存储计算机程 序， 所述计算机程序被 计算机执 行时， 实现权利要求1～7中任一权利要求所述的方法。权　利　要　求　书 2/2 页 3 CN 115525643 A 3