基于数据流的聚合函数精确计算研究及其应用

来源 :首都师范大学 | 被引量 : 6次 | 上传用户:sw_8818
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着网络的不断普及,流数据处理逐渐受到关注,流数据中的聚合计算也越来越重要。在传统数据库管理系统中,聚合函数定义为对一组值进行计算,并返回单个值的函数。在本文的研究中,我们仍然使用该定义。解决数据流中的聚合函数计算问题,对处理数据流,解决网络中的监控、统计、检测等问题具有现实意义。 本文主要贡献如下: (1) 对输入数据的类型为数值型的聚合函数,提出了一种存储最少数据的MAX函数和MIN函数的精确计算方法。这种方法是一种基于数据流滑动窗口聚合函数的精确增量式计算方法,它对于长度为N的输入序列,算法的时间复杂度为O(N);最坏情况下,空间复杂度为O(N),最好情况下,复杂度为O(M),其中,M为预先分配内存的大小。并通过数学理论分析和证明了该方法的正确性,还通过实验检验了该方法的有效性和实用性。最后还实现了COUNT、SUM、AVG、STDEV、STDEP、VAR、VARP等聚合函数的计算方法——增量式计算方法。 (2) 对输入数据的类型为字符型的聚合函数,实现了一种基于通用后缀树(GST)表示的字符串频率统计方法。该方法不需要任何训练,直接对接收的文本进行统计,并根据字符串的频率进行分类;对于长度为N的文本,算法的时间复杂度和空间复杂度均为O(N)。并应用对输入数据的类型为字符型的聚合函数的精确计算方法实现了一种基于后缀树的骨干网络垃圾邮件检测方法。该检测方法采用通用后缀树(GST)表示邮件文本;当新的邮件到达时,通过不定长统计方法计算该邮件和其他类别邮件的相似度,并确定邮件所属类别,然后利用聚合函数统计邮件重复出现的次数,最后判定该邮件是否为垃圾邮件。理论分析和实验表明该检测方法具有以下特点: ● 该方法充分利用了骨干网络的信息量大等特点,适合于骨干网络或大型服务器的垃圾邮件检测: ● 该方法独立于任何语种,适用于多语种邮件同时存在的情况。
其他文献
系统安全是一个愈来愈重要的问题,而审计系统作为隐患扫描、入侵检测系统等安全产品的重要补充部分,一方面有助于帮助安全管理人员有效地发现系统中的异常行为,从而防止重大
互联网的飞速发展,为快速的信息共享提供了一条简单有效的途径,大大提高了商业、科研、教育等行业的工作效率。与此同时,网络安全问题开始受到人们的重视。防火墙作为信息安
本文以Websphere MQ故障维护为应用背景,分析了目前Websphere MQ故障维护的现状和存在的问题的,结合基于案例推理技术的特点,将基于案例推理技术引入到Websphere MQ故障维护的研
随着计算技术和国际互联网的飞速发展,包括图象在内的各种多媒体数据的数量正以惊人的速度增长。现有的许多多媒体数据库系统只提供了基于媒体描述关键字的检索和查询,却忽略
随着网络上的知识的不断暴涨,如何能够快速而有效地按照用户的意图去获取网络资源,成为了一个十分重要而紧迫的问题.准确地获取资源就是要求搜索引擎能够搜集并根据用户自身
随着信息技术、网络技术的飞速发展,校园网的应用越来越广。校园内可以接入互联网的计算机的数量已经达到了相当的规模。校园网内已经有一些站点向校内的师生员工提供多样化的
报表可从海量的数据中提取有用的信息,清晰直观地呈现给管理人员或操作人员,以协助进行日常管理工作,规范生产活动。报表作为信息提取和显示的重要方式,已经得到广泛的使用。
随着多媒体技术、网络技术的迅速发展,图像信息的应用日益广泛,对规模越来越大的图像数据库中的可视信息进行有效管理成为迫切需要解决的问题,基于内容的图像检索是解决这一问题
软件的规模和复杂度不断增加,使得软件开发面临巨大的挑战.软件复用被视为解决软件危机、提高软件生产率和质量的可行途径.相比较而言,设计模式是高层次的软件复用,也更加切
随着无线通信技术、感知识别技术的发展,越来越多的研究者开始关注于客观世界物品与物品之间信息的通信与交换,物联网的概念也随之被提出。物联网融合了现存的互联网、移动通信