数据流滑动窗口查询处理技术地研究与实现

《数据流滑动窗口查询处理技术地研究与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、哈尔滨工业大学硕士学位论文数据流滑动窗口查询处理技术的研究与实现姓名：穆军申请学位级别：硕士专业：计算机科学与技术指导教师：宋益波20050601哈尔滨工业大学工学硕上学位论文摘要近年来，数据流广泛出现在多种应用领域中，例如传感器网络、股票分析、网络故障监测等等。与传统数据不同，数据流的特点是无限的、数据实时到来并且速度很快。数据流查询处理成为研究领域的一个热点研究方向。本文主要研究滑动窗口连续查询的处理问题。滑动窗口查询是数据流中一类重要的查询类型。根据执行方式的不同，滑动窗口查询可以分为元组驱动滑动窗口连续查

2、询和时间片驱动滑动窗口连续查询。作者提出了三种时间片驱动滑动窗口的连接算法：TDH(TimestampDrivenHash)、TDNL(TimestampDrivenNestLoop)、TDNH(TimestampDrivenNestHash)算法。针对滑动窗口聚集查询，作者提出了一种增量式元组驱动滑动窗口聚集查询处理算法TLDA(TupleDrivenAggregation)。TLDA利用前一次的聚集结果和查询两次执行之间滑动窗口的变化量来计算新的聚集值。与TLDA算法的思想类似，作者同时提出一种增量式时间片驱

3、动滑动窗口聚集查询处理算法TSDA(TimeStampDrivenAggregation)。在处理同一数据流上的多个滑动窗口聚集查询时，作者提出了共享滑动窗口聚集查询处理算法TLDSA和TSDsA，有效地节省了查询处理所需的主存资源。最后作者应用所提算法，设计并实现了一个滑动窗口连续查询处理原型系统一SWQS。SWQS系统采用多线程技术，并行处理用户提交的多个滑动窗口查询，能够在毫秒级响应用户的查询，能够满足数据流应用的实时性要求。理论分析和试验结果证明了本文所提方法是行之有效的。关键词数据流；滑动窗口；连接；聚

4、集彗尘鎏三些奎耋三兰竺：兰堡篓三AbstractRecently,datastreamsemergeinmanyapplicationsbroadly,suchassensornetwork，stockanalysisandnetworktrafficmonitoring．Fardifferentfromtraditionaldata,datastreamsareunbounded．real—timeandrapidarrivalrate．Datasteamqueryprocessinghasbeenanacti

5、veresearchaspect．Inthispaperweaddresstheproblemthathowtoprocesscontinuousslidingwindowqueryoverdatastream，whichisanimportantquerytypeofdatastreamqueries．Accordingtotheexecutionscheme，slidingwindowqueriescallbedividedintotwokindsofquery,theoneistupledrivenslid

6、ingwindowquery,andtheotheristimestampdrivenslidingwindowquery．Threealgorithms，namelyTDH，TDNLandTDNH,arepresentedinthispapertoprocesstimestampdrivenslidingwindowjoinquery．Forprocessingslidingwindowaggregationqueries，anincrementaltupledrivenslidingwindowaggrega

7、tionalgorithmTLDAisproposed，whichcomputestheaggregatefunctionusingthelastaggregationresultsandthechangingdataofslidingwindowbetweentwoexecutionsofquerySimilartoTLDA，TSDAalgorithmisalsopresented，whichcanprocesstimestanlpdrivenslidingwindowaggregationqueryeffec

8、tivelyToprocessmultipleslidingwindowaggregatequeriesefficiently,theauthorproposetwoalgorithmsTLDSAandTSDSAbasedonsharingslidingwindow,whichCansavememorygreatly．Basedonpresentedalgorithms，