论文部分内容阅读
随着网络的不断普及,流数据处理逐渐受到关注,流数据中的聚合计算也越来越重要。在传统数据库管理系统中,聚合函数定义为对一组值进行计算,并返回单个值的函数。在本文的研究中,我们仍然使用该定义。解决数据流中的聚合函数计算问题,对处理数据流,解决网络中的监控、统计、检测等问题具有现实意义。 本文主要贡献如下: (1) 对输入数据的类型为数值型的聚合函数,提出了一种存储最少数据的MAX函数和MIN函数的精确计算方法。这种方法是一种基于数据流滑动窗口聚合函数的精确增量式计算方法,它对于长度为N的输入序列,算法的时间复杂度为O(N);最坏情况下,空间复杂度为O(N),最好情况下,复杂度为O(M),其中,M为预先分配内存的大小。并通过数学理论分析和证明了该方法的正确性,还通过实验检验了该方法的有效性和实用性。最后还实现了COUNT、SUM、AVG、STDEV、STDEP、VAR、VARP等聚合函数的计算方法——增量式计算方法。 (2) 对输入数据的类型为字符型的聚合函数,实现了一种基于通用后缀树(GST)表示的字符串频率统计方法。该方法不需要任何训练,直接对接收的文本进行统计,并根据字符串的频率进行分类;对于长度为N的文本,算法的时间复杂度和空间复杂度均为O(N)。并应用对输入数据的类型为字符型的聚合函数的精确计算方法实现了一种基于后缀树的骨干网络垃圾邮件检测方法。该检测方法采用通用后缀树(GST)表示邮件文本;当新的邮件到达时,通过不定长统计方法计算该邮件和其他类别邮件的相似度,并确定邮件所属类别,然后利用聚合函数统计邮件重复出现的次数,最后判定该邮件是否为垃圾邮件。理论分析和实验表明该检测方法具有以下特点: ● 该方法充分利用了骨干网络的信息量大等特点,适合于骨干网络或大型服务器的垃圾邮件检测: ● 该方法独立于任何语种,适用于多语种邮件同时存在的情况。