论文部分内容阅读
近年来,随着新的数据采集方法的使用,产生了一种新的密集型数据集——数据流。由于数据流是连续、无限、随时间变化的数据序列,所以通常不便采用传统的数据库管理系统管理数据流。为解决数据流的管理问题,国内外学者进行了大量的研究,提出多种数据流模型,并实现了相应的数据流管理系统。然而,这些模型和系统往往只适合常规数据流的管理,不能很好地管理一些特殊的数据流。大域数据流作为数据流中的一种特例,其部分属性的取值范围很大,因此,所面临的管理问题比一般的数据流要严峻得多。 数据流应用场景对数据的处理速度要求很高。属性的取值范围很大,不仅会导致数据集庞大,还会增加概要设计的难度。相比一般的数据流而言,大域数据流的数据概要存储压力更大。本文首先基于最小计数概要(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算法的相对误差进行了比较全面的分析。实验结果表明,这两种算法均具有较好的可扩展性,能够适应大域数据流的应用场景。