基于共享滑动窗口的数据流查询处理算法的研究

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

1、哈尔滨工业大学硕士学位论文基于共享滑动窗口的数据流查询处理算法的研究姓名：潘立强申请学位级别：硕士专业：计算机科学与技术指导教师：李建中20050601哈尔滨工业大学工学硕士学位论文摘要近年来，随着信息技术的飞速发展，在许多应用领域均出现了一种称之为数据流的新型数据形式。例如传感器网络中传递的监测信号、互联网中流过的IP数据包、电信公司的通话记录、股票交易信息等等。这类数据的共同特点是数据持续到达且速度快，在时间维度上严格有序且规模宏大。由于在有限的存储空间中无法保存数据流的全部数据，同时数据流应用对查询处理有着很高的实时性要求，因此传统的数据库技术不适合对数据流进行管理

2、。目前，数据流管理技术的研究已经成为国际数据库研究领域的一个热点。本文着重介绍了基于共享滑动窗口的数据流查询处理技术。首先，提出了加权共享滑动窗口的概念，并在此基础上分别提出了三种优化的滑动窗口连接执行算法。其中LWF算法对于权值高的查询具有最快的反应速度；LWB算法平衡了各个滑动窗口上查询的执行时间，使权值较小的查询在数据流速较大的情况下也能够被执行到；MWT算法在单位时间内能够满足最多的系统权值，具有最大的系统利用率。其次，设计了基于共享滑动窗口技术的数据流聚集查询处理算法。该算法基于基本窗口的聚集信息，可以高效的计算滑动窗口内任意一段区间上数据的聚集值。在处理大量的

3、滑动窗口聚集查询时不但可以有效的节省存储空间而且同时减小了时间复杂度。再次，提出了适应数据流查询的操作符调度算法。该算法基于操作符——队列的处理方式，采用贪心算法思想，通过对查询计划中的各个操作算子进行分时调度来减小查询的内存开销和最大化查询结果输出率。最后，设计并实现了一个与平台无关，支持数据流上的滑动窗口连续查询，具有并发处理多个查询能力的数据流查询原型系统。理论分析和实验结果表明我们提出的方法是行之有效的，设计的原型系统构架简单、功能完备，直观的显示了各种数据流查询处理算法的计算结果。关键词数据流；查询处理；共享滑动窗口；连接；聚集AbstractRecently，

4、Anewmodelofdataappearsinmanyfieldwiththedevelopmentofinformationtechnology．Thismodelofdataiscalleddatastream．Examplesofsuchmodelofdataincludemonitorsignalsofsensornet，IPpackagesofnetwork，callrecordsoftelecomcompany,informationofstocktrading，andSO011．Thecommonalityofthiskindofdataisthatdat

5、aappearspersistently,rapidly,orderedintimedimensionandonaenormousscale．TraditionaldatabasetechnologyiSnotappropriatetothemanagementofdatastream，becausethewholestreamdatacannotbemaintainedinthelinfitedmemoryandtheapplicationofdatastreamrequiresqueryprocessingCallreflectquickly．Nowadays，the

6、studyontechniqueofdatastreammanagementhasbeenahotspotinthefieldofinternationaldatabaseresearch．Thispaperemphasizesonthetechniquesofthedatastreamqueryprocessingbasedonsharedslidingwindow．First，Weproposetheconceptofsharedweightslidingwindow,andthreejoinalgorithmsonsharedweightslidingwindowi

7、nthispaper．Amongthem．LWFalgorithmrespondsmostquicklytothequeryofhighweightvalue．LWBalgorithmbalancestheperformingtimeofqueryingoneveryslidingwindow,andmakesthequeryingofsmallweightvalueperformedunderthefastdatastream，whileMWTalgorithmcouldmeetthemostsystemweightvalu