数据流上若干查询处理算法的研究

《数据流上若干查询处理算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、织鳗大学博士学位论文数据流上若干查询处理算法的研究AlgorithmsforQueryingandProcessingoverDataStreams院系：信息科学与工程学院专业：计算机软件与理论姓名：金濑清指导教师：周傲英教授指导小组：周傲英教授薛向阳教授周本庚教授中文摘要过去十年中，数据流模型在一些信息处理应用中广泛出现．这些应用包括因特网、传感器网络、网络交通监控、计算机网络安全、数据挖掘、金融监控、制造业、天文等等。和传统数据模型相比，数据流模型具有几个截然不同的特征：(1)数据总量被假定为是无限的；(2)数据到达速率非常快；(3)数据到达次序不受应用所约束：(4)除非可以保存，每

2、个元素均只能够“看”一次。针对数据流模型的查询处理技术具有几点特殊要求。首先，该技术必须能够快速处理每一个元组，实时输出查询处理结果。其次，该技术的空间复杂度要低，因为数据流的规模被假定为是无限的而内存是有限的。再次，这类技术由于空间复杂度低、处理元组速率高．往往只能够得到近似解，但一般而言，该近似解都具备一定的精确度。最后，该技术适应性要强。数据流在某些应用中可能非常不稳定，不仅数据分布，而且流速都可能发生剧烈变化，“好”的数据流查询处理技术必须能够在各种状况下都具备良好的性能。传统的数据处理技术很难被应用到数据流模型中去。数据库管理系统(DBMS)需要先将所有数据保存起来，再提交查询

3、进行处理，难以满足实时应用的需求。另外一种处理技术是首先将所有数据全部载入到内存中，以随机访问的方式解决应用问题。但是由于数据流数据量远大于主机内存，该技术也不现实。这个现状迫使研究人员深入研究数据流模型。设计新的查询处理技术。本文针对数据流查询处理中的几个基本问题进行研究，并做出了以下几点贡献：1．如何挖掘数据流上的频繁元素是数据流研究的一个基本问题。我们提出了hcolInt算法来解决这个问题a该算法仅需要：·ln(一I笔)个计数器，就能够估算每个元素的值，且最大误差不超过E。我们还将hCount算法和一个空问时间索引结构(sRB·树)相结合，提出了stFreq算法，用于在空间时问流上

4、挖掘频繁元素。该方法空间复杂度低，查询精度高。2．估算分位数(quantile)问题也是数据流上的一个基本问题。我们提出T--种新算法，该算法仅仅需要挈-ln(一i兰)个计数器，就能够在包含delete操作的数据流上估算数据流中的分位数，且最大误差不超过t。相比而言，现有最好的同类算法也需要o((1092M)log(里华)／t2)[55]。3．计算数据流上的基数(cardinality)(或者说是相异元素个数)也是一个数据流研究的基本问题。很多应用还需要查询多流表达式的基数。本文中，我们提出了一种算法，它能够估算滑动窗口模型下多流表达式的基数。滑动窗口模型仅仅考虑每个数据流上最近的．Ⅳ个

5、元素。4．共享窗口连接(sharedwindowjoins)是数据流管理系统的一个基本操作。我们首先提出一种基于共享窗口连接的适应性元组调度策略(AS策略)，该策略能够根据在数据流突发(burst)时自动调整元组处理次序．从而最小化所有查询的平均响应时间。另外，在特定外部条件下数据流流速可能会远远超出系统处理能力，我们提出了两种面向共享窗口连接的降载策略：均匀降载策略和小窗口准确降载策略。这两种策略移除部分元组，实时输出查询结果，并且具有较好的准确度。总之，本文研究了四个数据流查询处理领域的基本问题，并且分别提出了新的解决方案。理论分析表明这些算法能够高效地解决相应的问题。本文还通过一系

6、列实验将新解决方案和前人研究成果进行比较。理论分析和实验报告表明，与现有数据流查询技术相比，上述算法在空间复杂度和结果准确性上有优势。因此，这些解决方案是对现有数据流查询处理技术的有益补充和改进。关键词：数据流模型，频繁元素，分位数。基数，连续查询，共享窗口连接分类号：TP301AbstractDatastreammodelhasappearedinagrowingnumberofinformation-processingapplicationsinthelastdecade，suchasinternet，sensornetworks，networktraf-ticmonitoring

7、，networksecurity,dataminingtfinancialmonitoring，manufacturing，chronometerandmanymore．Comparedwithtraditionaldatamodels，datastreammodelownsseveraldistinguishingcharacteristics，(1)thevolumeofastreamisnn-bounded，(2)therat