大域数据流管理技术研究

来源 :南京大学 | 被引量 : 0次 | 上传用户:gomo08
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
近年来,随着新的数据采集方法的使用,产生了一种新的密集型数据集——数据流。由于数据流是连续、无限、随时间变化的数据序列,所以通常不便采用传统的数据库管理系统管理数据流。为解决数据流的管理问题,国内外学者进行了大量的研究,提出多种数据流模型,并实现了相应的数据流管理系统。然而,这些模型和系统往往只适合常规数据流的管理,不能很好地管理一些特殊的数据流。大域数据流作为数据流中的一种特例,其部分属性的取值范围很大,因此,所面临的管理问题比一般的数据流要严峻得多。  数据流应用场景对数据的处理速度要求很高。属性的取值范围很大,不仅会导致数据集庞大,还会增加概要设计的难度。相比一般的数据流而言,大域数据流的数据概要存储压力更大。本文首先基于最小计数概要(Count-Min Sketch)技术,研究大域数据流的存储管理方法。  其次,由于数据采集传感器的性能、网络传输带宽及环境的影响,数据流普遍存在不确定问题。这种不确定问题通常表现为数据流的某些属性值的缺失。对于大域数据流中的缺失数据,难以采用邻近值填充等传统方法进行填充,也不能轻易删除。本文基于Count-MinSketch技术,提出最小频率概要(Frequency-Min Sketch),设计并实现了填充大域数据流缺失值算法(Fill Absent Value based on Count/Frequency-Min Sketch,FAV-CFM)。  第三,数据流的聚集查询是目前数据库领域的研究热点之一。聚集查询是数据流应用中一种重要且耗时的操作。而在一些典型的大域数据流应用中,数据的到达速率比一般的数据流更高(比如骨干网上的路由器每秒收到几百万个数据包),这给大域数据流上的聚集运算带来挑战。结合大域数据流的存储管理技术,本文认为,相比一般数据流而言,大域数据流的聚集查询算法对于时间复杂度和空间复杂度的要求更加苛刻。本文以Count-Min Sketch为基础,设计快照Count-Min Sketch算法,实现了大域数据流的多种聚集查询,包括基于时间段的聚集查询,理论上可以返回近期任意时间段的各种查询结果。  本文还通过实验分别对填充大域数据流缺失值的FAV-CFM算法和快照Count-MinSketch算法的相对误差进行了比较全面的分析。实验结果表明,这两种算法均具有较好的可扩展性,能够适应大域数据流的应用场景。
其他文献
随着IP技术的发展,流媒体技术和P2P技术被结合起来构成了一种可持续发展的网络服务——P2P流媒体。近年来电信核心网络的发展,需要一种能和IP网络相结合的可运营、可管理的在
随着油田勘探开发难度的不断加大,以及数据量的日益庞大,传统的油田技术已难以满足工程的需要,将油藏地层模型真实、形象地再现在计算机上,了解油层分布结构,以提高油藏采油率势在
量子程序设计语言是用于书写量子程序的语言,自1996年出现以来,颇受业界重视,它已经成为量子计算领域研究热点之一。  本文在明确研究宗旨、简述几种有代表性的量子程序设计语
错误定位技术因其重要性与困难性已经受到软件工程研究者的广泛关注,许多研究者提出了各种各样的错误定位方法,但都未能很好地解决软件的错误定位问题。针对错误定位,研究人员提
云计算是近年来广泛使用的一种能够将动态伸展的虚拟化资源通过互联网以服务的方式提供给用户的计算模式。在云计算中,业务运行在远程的分布式系统上,这个分布式系统由互联网
现代社会竞争激烈,人们对知识的更新与获取有了更高的要求,同时,计算机网络及信息科技的蓬勃发展带动了在线学习的浪潮。而作为一项非盈利性事业,为了能够持续开展大规模的在
随着移动通信业的发展以及计算机网络的成熟,融合通信的概念开始被人们提及,并逐渐成为了一种新的通信模式。融合通信,即融合计算机网络与传统通信网络于一个网络平台上,以实
软件公司控制软件成本和追求利润的本质,软件开发从业人员的疏忽,以及软件测试的不可穷举性等,都造成了程序漏洞的不可避免性。其中最常见的是与非法篡改内存相关的程序漏洞,包括
程序插装是联系静态分析与动态测试的关键桥梁,是实现软件自动化测试必不可少的关键步骤。通过程序插装进行动态测试,可获得程序的执行路径、覆概率、运行时间等动态信息,在软件
游戏的核心是游戏引擎,游戏引擎是一个处理游戏底层技术的平台,用于控制游戏中所有的功能,包括游戏的系统架构、内存管理、图形图像渲染、物理引擎、网络、输入输出等。可以说,游