一种数据流连续查询的并行处理技术

《一种数据流连续查询的并行处理技术》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第41卷增刊2004年10月计算机研究与发展JOURNALOFCOMPUTERRESEARCHANDDEVELOPMENTVo

2、．41，supplOct．2004一种数据流连续查询的并行处理技术王伟平1李建中L2张冬冬1郭龙江1‘2王栩11(哈尔滨工业大学计算机科学与技术学院哈尔滨150001)2(黑龙江大学计算机科学与技术学院哈尔滨150080)(wpwang@hitedu．C11)摘要由于连续查询具有很高的实时性要求，数据流上连续查询的处理算法均是主存算法。在处理复杂的滑动窗口连续查询时，滑动窗口数据以及查

3、询处理的中间结果难以全部保存在主存中．已有的解决方法是对滑动窗口数据进行抽样，在抽样数据上处理查询，这种方法的缺点是只能给出滑动窗口查询的近似查询结果．应用机群并行技术处理滑动窗口的连续查询，有效地解决了复杂滑动窗口连续查询处理的主存溢出问题．提出了几种连续查询操作的并行实现算法，给出了并行连续查询计划的表示模型和优化的并行查询计划生成算法，理论分析和实验结果表明本文提出的方法是有效的．关键词数据流；并行；连续查询；滑动窗口中图法分类号TP311AParallelMethodforProcessingConti

4、nuousQueriesonDataStreamsWangWei—Pin91，LiJian—Zhon91一，ZhangDon．g—Don91，GuoLong．Jian91仙，andWangXu1(SchoolofComputer&ien，eandTechnology，HarbinInstituteoyTechnology，Harbin150001)2(SchoolofComputer＆慨andTec'hmology，HeilongjiangUniversity，HaJ-bin150080)AbstractSin

5、cethecontinuousqueryhasreal—timerequirements，itsevaluatingalgorithmsarememory-only．WhenprocessingcomplexslidingwindowqueryoverdatastroxaTns，thespacerequirementsforprocessingcarlbebeyondthememory．Asolutionforthisissueissamplingslidingwindowdata．However，thisme

6、thodcanonlygivetheapproximatequeryresultsforthequeries．Aparallelslidingwindowqueryprocessingmethodispresentedinthispaper，whichcansolvethememoryoverflowproblemefficiently．Severalnovelparallelalgorithmsforcontinuousqueryoperatorareproposed．Aparallelcontinuousq

7、ueryplanmodelandcorrespondinggeneratingalgorithmsarealsopresented．Theoreticalanalysisandexperimentalresultsshowthatthemethodpresentedinthispaperiseffective．Keywordsdatastrealll；parallel；continuousquery；slidingwindow1引言近年来，在很多应用领域出现了一种称之为数据流的新型数据模式，如各类传感器检测到的

8、数据、互联网中传递的IP数据包、Web服务器上的用户登录记录、电信公司的通话记录等．数据流上的查询主要是连续查询．连续查询注册到系统后，随着数据流上新数据的到来而不断返回查询结果．除非用户发出指令撤销该查询，否则连续查询将不断地被执行，连续查询具有长期运行的特点．由于数据流应用对连续查询具有很高的实时性要求，因此连续查询的处理算法都是主存算法．数据流无限性的特点使得许多连续查询在有限的内存中无法计算出收稿日期：2004—07—15基金项目：国家自然科学基金项目(60273082)；国家“八六三”高技术研究发展计

9、划数据库重大专项基金项目(2002AA444110)；黑龙江省自然科学基金重点项目(弓903_(15)计算机研究与发展2004芷精确结果．例如处理数据流上的连接查询，系统需要在主存中保存每个数据流的连接状态，而这需要无限的主存空间．为了解决这类连续查询的处理问题，研究人员提出了滑动窗口技术．滑动窗口是指在数据流上设定的一个区间，该区间只包括数据流最近的部分数据．随着新数据的到来，窗口向