不确定时间序列的编码匹配

《不确定时间序列的编码匹配》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、总第289期计算机与数字工程VolI41No．112013年第11期Computer&DigitalEngineering1797不确定时间序列的编码匹配肖瑞刘国华宋转刘玉静(东华大学计算机科学与技术学院上海201620)摘要由于时间序列的长度很大，并且不确定时间序列在每个观察点的取值具有不确定性，这导致了维度灾难和庞大的可能世界集，给不确定时间序列相似性匹配带来了巨大的困难。针对此问题，提出一种基于桶分割和算术编码的相似性匹配算法，该算法不仅可以将不确定时间序列规约为一条确定的时间序列，并通过距离度量完成相似性匹配，而且可以通过规约后的

2、确定时间序列近似地恢复原不确定时间序列。最后实验验证，使用该算法对不确定时间序列进行相似性匹配，不仅有很高的匹配效率和很低的时间复杂度，而且可对两种新的相似性类型完成匹配。关键词时间序列不确定性；匹配；桶；算术编码中图分类号TP31iDoI：10．3969／j．issn1672—9722．2013．11．026EncodingSimilarityMatchingforUncertainTimeSeriesXIAORuiLIUGuohuaSONGZhuanLIuYunjing(CollegeofComputerScienceandTechn

3、ology，DonghuaUniversity，Shanghai201620)AbstractBecausethe1engthofuncertaintimeseriesisverylong，andthevaluesineachobservationpointareuncertain，itleadstotheCurseofDimensionalityandhugepossibleworlds，inaddition，itarouseshightimecOStandloweficiencywhenmatchinguncertaintimese—

4、ries．Tosolvetheproblem，thematchingmethodbasedonbucketdivisionandarithmeticcodingisproposed．Thealgorithmcanreduceun—certaintimeseriestocertaintimeseriesandmatchtimeseriesbydistance．Italsocanapproximatelyrecovertheuncertaintimeseriesbyre—ducedoutcomes．Atlast，theexperimentpr

5、ovesthatthealgorithmownslowtimecostandhighmatchingefficiency．Inaddition，itcanmatchtwonewtypes．KeyWordstimeseries，uncertainty，matching，bucket，arithmeticcodeClassNumberTP31]的_g]，他将该问题定义为：在大规模的时间序列数据库里，1引言通过一定的相似性匹配方式，查询出和已知序列相匹配的时间序列(TimeSeries，TS)是按时间顺序排列的实数时间序列集合。序列，它反映了实

6、体属性在时间顺序上的特征。近年来不2008年文献El0]首次了提出不确定性时间序列相似确定性数据管理逐渐成为数据库领域的研究热点_1q]，但性匹配问题及不确定性时间序列高维度的一种通用模型关于不确定时间序列的研究才刚刚起步。不确定时间序列——c1oakedtimeseries。该模型假设在序列的每个采样匹配在位置定位(LocationBasedService，LBS)系统、环境点，随机变量的描述信息仅知其均值和方差，提出隐式范围监测、物联网等领域中有广泛的应用，但是现有的对不确定查询方式(cloakedrangequery，CRQ)，并使

7、用U-tree[]索时间序列进行相似性匹配的算法普遍存在时间复杂度高和引进一步提高匹配的效率。匹配效率低的问题_1]。文献El1]提出了不确定性时间序列的相似性匹配方本文主要研究了不确定时间序列基于桶分割和算术编法。将不确定时间序列视为多维空间中的不确定性向量，码的相似性匹配问题。首先通过桶分割和符号映射，将不并且序列之间的距离也是不确定的，据此得出不确定时间确定时间序列每个时间点的观察值映射为0／1符号串，然序列之间的欧式距离和动态时间弯曲距离表示法，且提出后对每个观察点的0／1符号串进行算术编码，构建为确定了不确定性时间序列的两种查询

8、方法，即概率性的有界范时间序列并通过欧式距离度量完成相似性匹配。最后提出了两种新的相似性类型，并通过实验验证编码匹配算法可围查询(probabilisticboundedrangequery，