一种关于数据流区间Disjoint查询的快速处理算法.pdf

《一种关于数据流区间Disjoint查询的快速处理算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、计算机研究与发展DOI：10．7544／issn1000—1239．2014．20121092JournalofComputerResearchandDevelopment51(5)：1136—1148，2O14一种关于数据流区间Disjoint查询的快速处理算法王少鹏闻英友李志赵宏(东北大学信息科学与工程学院沈阳110819)(wangshaopeng1984@163．corn)AFastProcessingAlgorithmonSectionDisjointQueryofDataStreamWangShaopeng，WenYingyou，LiZhi，andZ

2、haoHong(CollegeoJInformationScienceandEngineering，NortheasternUniversity，Shenyang110819)AbstractDisjointqueryhasplayedaveryimportantroleintheresearchaboutsimilaritymatchoversubsequenceofdatastream，suchassensornetwork，dataminingandSOon．Buttheexistingresearchdidnotfocusonthedisjointque

3、rywhichisexecutedforelementsofdatastreaminthefixed—lengthsection．RunningSpringalgorithmforalltheelementsineverysectiondirectlyistheNAIVEalgorithm．Butthisalgorithmdoesnothavethecharacteristicofincrementalcomputation，SOithasredundantoperation．Theboundarypathtechnologyisproposedinthispa

4、pertodealwiththisredundantoperation．TheNAIVEalgorithmcangetthedisjointqueryresultsofcurrentsectionbasedontheonesofprevioussectionandneednotperformingforeveryelementincurrentsectionbyusingthistechnology，SOithasthecharacteristicofincrementalcomputation．TheFSDQalgorithm，whichhasthechara

5、cteristicofincrementalcomputation，isproposedbyimprovingNAIVEalgorithmwiththeboundarypathtechnology．ExtensiveexperimentsonrealandsyntheticdatasetsshowthattheFSDQalgorithmisaneffectivewaytosolvetheproblemofsectiondisjointqueryoverdatastream，anditcanreduceredundantoperationstheNAIVEalgo

6、rithmhasandmeettherequirementsofpracticalapplication．KeywordsDisjointquery；Euclideandistance；dynamictimewarping(DTW)；datastream；Springalgorithm摘要在关于数据流子序列相似性匹配的研究中，Disjoint查询是很重要的一类，在传感网络和数据挖掘等方面都发挥着非常重要的作用．但现有的研究并没有关注到定长区间上的Disjoint查询问题．直接对每个区间内成员使用Spring算法是解决该问题的NAIVE算法，但是因为NAIVE算法

7、不具有增量计算的特点，所以存在冗余运算．针对NAIVE算法冗余运算的处理问题，提出了边界路径技术．边界路径技术很好地使用了Spring算法在相邻前一区间上的执行结果，使得Spring算法无需对当前区间上每个成员执行，就可以得到Disjoint查询在该区间的查询结果．使用该技术对NAIVE算法进行改造，设计并实现了快速区间Disjoint查询处理算法(fastsectionDisjointqueryprocessingalgorithm，FSDQ)，该算法具有增量计算的特点．实验证明FSDQ算法可以有效减少NAIVE算法所具有的冗余运算，是处理数据流上区间Disj

8、oint查询的有效方法．