第  40 卷  计  算  机  学  报  Vol. 40 2017 论文在线出版号  No.47  CHINESE JOURNAL OF COMPUTERS  2017 论文在线出版号  No.47 ——————————————— 本课题得到国家自然基金重点项目《大数据管理系统评测基准的理论与方法》(No. 61432006)和国家重点研发计划面向高端制造领域的大数据管理系统项目(No.2016YFB1000700)的资助.  周宁南，男，1990年生，博士研究生,主要研究领域为数据库、数据挖掘.E-mail: zhouningnan@gmail.com.  张孝（通讯作者），男，1972年生，博士，副教授，计算机学会(CCF)会员（10279S）,主要研究领域为数据库、大数据.E-mail: zhangxiao@ruc.edu.cn.  刘城山，男，1992年生，硕士研究生，主要研究领域为数据库.Email:964912846@qq.com.  王珊，女，1944年生，硕士，教授，计算机学会(CCF)会员（00023F）,主要研究领域为数据库、大数据.E-mail: swang@ruc.edu.cn. 基于动态时间规整的时序数据相似连接 周宁南2)  张孝1),2)  刘城山1),2)  王珊1),2)  1)(  教育部数据工程与知识工程重点实验室(中国人民大学) 北京  100872)   2)(  中国人民大学信息学院  北京  100872) 摘  要  由于蕴含事物发展规律，时序数据上的数据挖掘正成为大数据决策的重要组成部分。作为时序数据挖掘的一种基本操作，时序数据相似连接可以找出给定相似度度量下的所有相似时序数据对。研究表明，动态时间规整(Dynamic  Time Warping, DTW)正在文本挖掘、趋势预测等越来越多的科学与社会应用领域中成为时序数据上目前最佳的相似性度量方法。本文首次提出采用DTW作为相似性度量方法的时序数据相似连接问题。特别地，我们首次提出了基于阈值和基于top-k的两种DTW度量上的时间序列相思连接任务。除了服务于进一步的时序数据挖掘算法，这两个任务还具有机器翻译、关联检测等广泛的直接应用。但是，直接的相似连接方法因为时序数据的规模大、DTW计算复杂性高而不能在实际中工作。尽管存在很多基于DTW的索引和上下界计算方法，这些工作主要关注DTW度量上的快速检索而非相似连接。因此，这些方法都假设存在一个固定的时序数据作为查询，并根据查询使用时间和空间复杂度很高的方法构建索引或进行预计算。但在我们的相似连接问题中，所有时序数据都是查询，因此这些方法的构建索引和预计算的时间比直接的相似连接方法需要的处理时间还长。为此，我们针对两种相似连接任务提出了两个基于DTW上下界的剪裁框架用于减少准确DTW相似性的计算次数。基于划分，我们为DTW度量设计了新颖的上下界计算方法。由于细粒度的划分带来上下界接近准确的DTW相似性但需要更长的计算时间，而粗粒度的划分需要更短的计算时间和与准确DTW相似性有较大差距的上下界，我们设计了基于二分查找的机制来自动找到合适的划分粒度，实现了整体的高处理性能。面对单机不能容纳全部时序数据和运行时间长的情况，我们将提出的两种相似连接处理框架利用MapReduce并行计算框架扩展到了分布式环境。我们在两个真实数据集上验证了本文提出的DTW相似连接在实际应用中的效果，并在真实与合成数据集上进行了充分的实验，验证了本文方法的高效性。 关键词  动态时间规整；时间序列；相似连接   中图法分类号  TP311   论文引用格式：   周宁南,张孝,刘城山,王珊,  基于动态时间规整的时序数据相似连接,2017, Vol.40,在线出版号  No.47 ZHOU Ning-Nan,ZHANG Xiao,LIU  Cheng-Shan,WANG Shan, Similarity  Join  on  Time  Series  under  Dynamic  Time Warping, 2017, Vol.40,Online Publishing No. 47  Similarity Join on Time Series under Dynamic Time Warping ZHOU Ning-Nan2)  ZHANG Xiao1),2)  LIU Cheng-Shan1),2)  WANG Shan1),2)     1)( Key Laboratory of Data Engineering and Knowledge Engineering of the Ministry of Education (Renmin University of China), Beijing 100872) 2)( Department of Information, Renmin University of China, Beijing 100872) Abstract  Revealing evolution insights of things, time series mining is becoming an indispensable component of big data driven decision making. As a fundamental operation in time series mining, given a similarity measure, similarity join gathers all pairs of similar time series. It is demonstrated that DTW (Dynamic Time Warping) has 网络出版时间：2017-04-21 10:09:15网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170421.1009.002.html2  计  算  机  学  报  2017年 served as  the best  measure  in  disparate domains  ranging from  scientific to social  fields  such  as text  mining or tendency prediction. In  this  paper,  we  for  the  first  time  propose to  join  similar  time  series  with DTW as  the similarity  measure. Specifically, we for the first time define two tasks, the threshold based and the top-k based similarity join under DTW. Besides to serve time series further mining tasks such as stock prediction, these two tasks can be directly applied to a wide spectrum of applications such as machine translation and delay-correlation detection. Unfortunately, trivial solutions suffer from the large scale nature of time series and high computational complexity  of  DTW. Numerous  indexing  techniques and  various  lower  and  upper  bounds  of  DTW have  been proposed. However, these works aim at similarity search rather than similarity join under DTW. In concrete, they assume  that  a  fixed  time  series  serves  as a query and  index  or  precomputation  is  performed  on  the  query time series.  It  is  time  and  space-consuming  to  construct  index and  precompute for the  fixed time  series.  However, under  our  similarity  join  task,  all  time series  serve  as  the  fixed  query  and  thus  the index  construction  or precomputation time for  all the time  series is  even  beyond  the  execution  time  of  the  trivial  solution and  thus these techniques  become  impractical. To  tame  similarity  join  under  DTW,  we  first  propose  two  pruning  based processing  frameworks  for  the  threshold-based  and  top-k  based  similarity  join  tasks  respectively. These  two frameworks  prune  unnecessary  calculation  of  accurate  DTW similarity between  time  series  by  leveraging  the cheap upper and lower bound of DTW measure. In this way, we further devise novel upper and lower bounds for DTW measure. Both bounds are developed on top on time series partition. Since fine-grained partition enables more accurate DTW similarity but consumes  more execution time while coarse-grained partition results in less accurate DTW similarity but consumes less execution time, we develop a mechanism based on binary search to quickly tune the granularities of partitions automatically and thus enable the overall practical performance. When single machine cannot meet the requirement of performance or cannot hold the massive time series, we extend our processing frameworks to distributed environment. Specifically, we design a MapReduce implementation to our pruning based similarity join framework. We conduct extensive experiments to demonstrate the effectiveness and efficiency of our methods. First, we apply the two proposed similarity join tasks on two real world datasets to  demonstrate  that  the  threshold-based  similarity  join  task  can  be  used  to find  correlated  power supplement sources and find the same entities in different languages. Then, we use both real world and synthetic datasets to demonstrate that  our  methods  outperform  existing  solutions  consistently  under  various  lengths and  volume  of time series. Key words  dynamic time warping; time series, similarity join 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  3  1  引言 随着大数据时代的到来，人们获得了诸如供电负荷走势、文本序列等社会和科学各领域的大规模时序数据。例如，电网中各个供电设备的输出功率每15分钟由传感器记录一次，这样一个设备一年就积累长度超过60/15小时×24小时/天×365天≈35000的时间序列。由于时序数据蕴含了事物发展的规律或特点，将具有相似变化趋势的时序数据聚集在一起可以挖掘其中的相关性、主旨等规律[1-4]，进而为基于大数据的决策提供依据。 DTW（Dynamic Time Warping，动态时间规整）在时序数据的大部分应用领域中被证明是最佳的相似性度量方法[1,5]，其普适性得到超过800篇论文的验证，没有其他度量方法显著优于它[6,7]。DTW在下面两个实际数据集上的应用说明了本文将要提出两类具体任务。 例1．图1是三个供电设备从1月1日到1月14日每天采样一次供电功率得到的供电功率变化曲线。可以看出的规律是，设备3的曲线向右平移三天就能够和设备1的曲线基本重合。这种时间上滞后的关联性可以被DTW捕捉到。这样，给一个较小的阈值(比如5)，设备1和设备3将成为DTW相似连接的结果。利用此结果，电网公司可以通过比较某个时刻设备1和三天前设备3的供电功率判断是否供电异常。  图1  三个供电设备14天内供电功率的时序数据 例2．图2是具有相同意义的词汇在不同语言的同一著作中出现频度的时序数据。我们将著作以100个单词为单位切割成连续的片段，并记录给定单词在每个片段中出现的次数。尽管著作的不同语言的版本具有不同的语序、词汇数，DTW可以捕捉到图2(b)与时间轴上被压缩了的图2(a)十分相似。如果我们将每个词汇与它们最相似(Top-1)的时间序列相连接，连接结果将显示每对对应不用语言中相同意义的词汇，这为利用统计的机器翻译中进行双语词汇匹配提供了帮助[8]。  (a)英文版“God”一词在每100个词汇中出现的频度，横坐标表示给定单词在切割后的单词片段中的位置   (b)中文版“上帝”一词在每100个词汇中出现的频度，横坐标表示给定单词在切割后的单词片段中的位置 图2 中英文词汇在同一著作中出现频度的时序数据 上面的两个例子体现了对时序数据进行基于阈值和Top-k的相似连接在数据挖掘中具有重要应用。总结这两类任务，本文首次提出了基于DTW的相似连接这样一个新的查询问题，并主要考虑基于阈值和基于Top-k的DTW相似连接这两种具体任务。 计算DTW的时间复杂度较高，为O(2n)，其中n是时序数据的长度，而我们面对的时序数据通常很长，通常超过104，这为基于DTW的时序数据相似连接带来了极大的挑战。现有的相似连接和DTW相似搜索两方面工作都具有不足。 相似连接问题通常采用“过滤-验证”框架[9,10]，即过滤阶段将每个时序数据与和它可能成功连接的若干时序数据组成时序数据对加入候选集合；验证阶段为每对候选集合中的时序数据对计算DTW值，确定最终的连接结果。然而，此框架通常针对字符串相似连接，现有的基于前缀过滤或分段过滤等字符串相似连接技术在DTW相似连接问题中存在两个缺陷：(1)时序数据的长度通常超过104，验证阶段用时较长；(2)由于具有不同的数据类型和相似性度量方式，现有技术不能直接应用在DTW相似连接上。 另一方面，DTW相似搜索对查询时序数据进行变换，而在相似连接时对全部时序数据进行变换会导致较高的时间和空间代价。其他工作通过牺牲DTW计算上的准确度，以随时序数据长度线性增长的计算代价得到给定时序数据对的近似DTW。这样不仅造成连接结果不准确，而且由于时序数据较长，对全部时序数据对计算近似DTW依然需要较长时间。 为了克服上述困难，本文采取使用较少时间为每对时序数据计算DTW相似度的上下界的方式避免计算所有时序数据对的准确DTW，从而提高相似连接的性能。特别地，本文提出了两个新颖的算法分别用于快速计算任意一对时序数据的DTW上界和下界。具体地，我们采用基于划分的方法比准确DTW计算的时间成倍地减少了计算时序数据DTW上界的时间。我们还考虑时序数据的取值分布以O(n nlog)的时间复杂度计算一对时序数据的DTW下界。这既减少了需要计算准确DTW的时序数据对个数，又实现了比计算近似DTW还低的计算代价。 本文贡献如下： (1)  首次提出基于DTW的时序数据相似连接问题，并分4  计  算  机  学  报  2017年 别定义基于阈值和基于Top-k的两个DTW时序数据相似连接任务。 (2)  提出两个新颖的DTW上界和下界计算方法，高效地解决了本文提出的两种基于DTW的时序数据相似连接问题。 (3)  使用真实的电网数据和文本数据验证了基于DTW的时序数据相似连接问题的实际应用需求。 (4)  在真实和合成数据上进行的充分实验验证了本文提出的基于DTW相似连接的性能和所提出的两种上下界计算方法的效果。 本文第１节描述问题的背景和意义；第２节介绍问题定义；第3节介绍相关工作；第4节给出基于DTW相似性度量方法的相似连接算法；第5节使用实验来验证所提问题的实际应用效果和算法效率；第6节总结全文以及提出未来工作。 2  问题定义 我们首先定义本文所处理的时间序列数据，然后定义DTW相似度的一个特例：欧几里得距离，最后定义DTW相似度和基于DTW的相似连接。 定义1.  一个时间序列T是一个长度为m的有序列表] , , , [1 1 0 - =mt t t T K，这里m T =。 例如，表1分别展示了图1中设备1、设备2和设备3的时间序列1T，2T和3T。 定义2.  时间序列iT和jT(j iT T =)上的欧氏距离被定义为å-=- =102]) [ ] [ ( ) , (mkj i j ik T k T T T ED 根据定义2，如图3(a)所示，长度相同的时间序列1T和3T间的欧式距离是按黑色虚线将两个序列一一对应后，相应差值(黑色虚线投影到Y轴的长度)的平方和的算数平方根。可以看出，1T和3T在欧式距离上较大的差异主要来自于12个数值差异较大的数据点对。但这样的数据点一一对应得到的两条时间序列上的距离并不能真实反应实际情况中两条时间序列的相似性。例如，时间序列1T和3T实际表示在时间上有延迟的相同的变化趋势。当我们将3T向前移动三天，我们可以发现1T和3T是重合的。这样在时间上具有延迟效应的相似变化趋势在实际中比较常见，除了例1中供电负载变化由于供电线路造成的具有延迟3天的相关性外，例2中不同词汇由于中英文表达相同文本所用单词量不同，也造成含义相同的词汇得到的时序数据具有延迟相似的效应。为了发现时序数据上具有延迟效应的相似变化趋势，DTW相似度被广泛采用。 与欧式距离将两个时间序列一一对应不同，DTW相似度允许序列中多个点对应到另一个序列的一个点，再将两个序列最优对应下的差值平方和的算数平方根作为相似度。 为了将长度分别为n和m的时间序列iT和jT进行对应，DTW 构建一个m n´的矩阵w，其每个元素2]) [ ] [ ( ] , [ c T r T c r wj i - =表示] [r Ti与] [c Tj对应时的欧式距离。 这样，如图3(b)中实心方块所示，两个序列的一个匹配就对 应 于 矩 阵 元 素] , [p p pc r w w =的一条路径是] , , , , , , [1 2 1 q p p w w w w w K K+, 其中m n q m n + £ £ } , max{。DTW中路径需要满足的条件是: (1)路径必须以矩阵的左下角元素和右上角元素作为起始和终止，即] 0 , 0 [1w w =和] , [ m n w wq=。 (2)路径中元素必须向相邻元素转移，因此路径中相邻的元素] , [p p pc r w w =和] , [1 1 1 + + + =p p pc r w w要满足1 1 1 ,+ + = + =p p p p r r c c， 或1 1, 1+ + = = +p p p p r r c c, 或1 1 1 , 1+ + = + = +p p p p r r c c。 定义3. 给定时序数据iT和jT，它们的DTW相似度是所有满足条件的路径的差值平方和的算数平方根中的最小值，即 } { min ) , ( åÎ=path wppathj ipw T T DTW 对于时序数据iT和jT，动态规划的转移方程 ( ) [ ] ( ) ( ) ( ) { } , , min 1, , , 1 , 1, 1 r c W r c i j i j i j g g g g = + - - - -可以得到差值平方和最小的路径对应的DTW值) , ( n m g。值得注意的是，越小的DTW相似度意味着两条时序数据越相似。图3(b)中实心方块表示了时序数据1T和3T间的最优对应。对比图3(a)的欧氏距离，1T和3T间较小的DTW相似度只由三个黑色方块表示的具有较大差异的数据对构成。这与图1中1T和3T具有相似的变化趋势相吻合。 下面分别定义例1和例2中的相似连接任务。 定义4(基于阈值的DTW相似连接).  给定时序数据集合1S,2S和阈值q，基于阈值的相似连接返回所有时序数据对（iT,jT），其中q £ Î Î ) , ( , ,2 1 j i j i T T DTW S T S T。 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  5  定义5(基于Top-k的DTW相似连接).  给定时序数据集合1S,2S和整数k，基于Top-k的相似连接对1S TqÎ "返回一个子集2S S Í,k S =, 对S S T S Tj i - Î " Î "2 ,,) , ( ) , (j q i q T T DTW T T DTW £。 例如，阈值5 = q时，1S和2S都是例1中配电曲线集合的基于阈值的相似连接将具有延迟三天关系的数据对<设备1,设备3>作为查询结果；1 = k时，1S和分别是例2所示的英文和中文词汇的时序数据的Top-1 相似连接将两种语言中具有相同含义的词汇对作为查询结果。  表1 设备1、设备2和设备3的时序数据   长度=14的时间序列 设备1(1T)  121  779  781  769  121  103  131  786  779  781  122  121  103  789 设备2(2T)  789  235  679  262  647  228  697  212  691  206  645  246  613  240 设备3(3T)  121  103  131  131  789  781  788  121  103  131  786  779  781  769 121 103 131 131 789 781 788 121 103 131 786 779 781 7697891031211227817797861311031217697817791211T3T121 103 131 131 789 781 788 121 103 131 786 779 781 769789103121122781779786131103121769781779121] 0 [1T ] 1 [1T ] 0 [3T ] 1 [3T (a)设备1与设备3之间的欧式距离                    (b) 1T和3T间的DTW距离                      (c) 1T和3T的DTW上界 图3  设备1与设备3间的DTW相似度  3  相关工作 本文首次提出基于DTW的相似连接问题，其相关工作主要包括两类：基于DTW的搜索问题和针对其他数据类型或度量方式上的相似连接问题。 3.1 基于DTW的搜索问题 基于DTW进行相似搜索的工作主要提出了计算两条时间序列的DTW相似度下界的方法[11-16]和近似计算DTW的方法[17-20]。其中，Kim下界计算给定时序数据与待匹配子时间序列间首尾数值以及最大值之间的差异之和，并以此作为DTW相似性的下界[9]。Yi下界首先找出两条序列中最大值较小的序列，并对另一序列中所有高于这个值的数据与其差值作为两条时序数据DTW相似度的差值[12]。最新的工作Keogh下界则将长度为m的时间序列通过循环置换重写成m个长度为m的时间序列，并得到紧的DTW下界[13]。 近似计算DTW的方法通过避免构建完整的矩阵w来高效计算近似DTW相似度。其中，基于封装的方法将时序数据映射成近似的向量，并基于向量构建矩阵上的路径[18,21]。FastDTW只计算w中偏离对角线较小的区域内的路径[17] 0，Local  DTW只允许计算以w的对角线为对角线的窄平行四边形范围内的路径[18]。 这些计算DTW相似性下界的方法和近似计算DTW的方法并不能直接应用于本文的问题。对于计算DTW相似性下界的方法来说，尽管理论上我们可以对每条时序数据用计算DTW相似性下界的方法裁剪掉不可能成为相似连接结果的时序数据，实际上现有方法中得到的紧的DTW下界的方法依赖DTW查询中查询序列较短的假设，这在相似连接问题中是不适用的。例如，在实验数据集上目前最好的Keogh下界[13]将长度为m的时间序列重写为m个长度为m的时间序列所需的空间远远超出整个实验数据集的大小。此外，其他如Kim下界和Yi下界只考虑了若干时序数据中的特征，而本文提出的下界考虑了更为全面的数值分布特征，因此得到了更好的下界。计算近似DTW的方法由于牺牲了准确性，可以作为本文的补充，在应用对DTW相似度准确性不敏感的情况下使用。 3.2  其他数据类型上的相似连接问题 本小节主要涉及字符串上的相似连接问题和集合上的相似连接问题。 6  计  算  机  学  报  2017年 针对集合上的相似连接问题，文献[22]提出了将集合元素排序后进行前缀过滤的方法。文献[23]对此方法的基础上使用位置过滤和后缀过滤改进了前缀过滤的效果。特别地，他们发现如果两个集合对在基于阈值的相似连接结果中存在，这两个集合的不同元素不应超过由阈值导出的一个数值。文献[24]考虑了更多因素进一步增强了前缀过滤的效果。文献[25]为基于Jaccard 相似性和编辑距离等不同相似性度量方式的集合连接问题提出了一般的解决方法。文献[26]为数据库增加了划分和枚举两个操作符实现了数据库中的集合相似连接操作。文献[27]扩展了前缀过滤技术实现了基于top-k的集合相似连接。文献[28,29]在分布式计算框架MapReduce上实现了集合相似连接。 针对字符串上的相似连接问题[30]，文献[26,31]提出了一种新的操作符，并使用SQL语句在关系数据库中进行字符串相似连接操作。文献[32]提出一种可以过滤掉不可能作为相似连接结果的字符串对的签名方法。文献[33]提出了基于转化的框架来定义不同相似字符串的方法来完成相似连接。最近的工作通常使用“过滤-验证”机制[34]，并应用前缀过滤[35]、分段过滤[36]等技术进行字符串上的相似连接。 尽管我们可以将时序数据视为字符串甚至集合，但由于两两集合元素或两两字符串之间只有相同和不同关系，而时序数据间由于不同的数值间有差距大小的关系，因此基于集合或字符串的相似连接方法并不能直接应用于本文定义的基于阈值或基于top-k的相似连接问题。 3.3  其他度量方式上的相似连接问题 除了基于集合和字符串上的相似连接使用Jaccard 相似性、编辑距离等于DTW不同的相似性度量方法外，基于时序数据的其他工作还有利用欧式距离等相似性度量方法进行相似连接的方法。 文献[37-39]使用R树或空间哈希等方法为数据库中的时序数据的子序列建立索引，然后利用索引进行连接操作。特别的，文献[36]为每个数据库建立一棵R树，使用深度优先的方法搜索R树，最后得到叶子节点的相似子序列对。文献[38]使用广度优先的方法提升了这种方法的性能。文献[39]将子序列哈希到不同数据桶中并使用不同桶中的子序列作为连接候选结果。这些方法一般用于度量方式是准确连接的时序数据连接任务。由于大体相似但有细微不同的时间序列会被映射到不同的R树叶子节点或不同的哈希值，这些方法不能直接应用于本文的相似连接任务。 还有部分工作考虑流数据上如何使用少量内存对最近的时序数据进行连接[40]和图数据上基于编辑距离的相似连接问题[41]。但前者是基于欧式距离的相似连接方法[40]，后者使用节点间路径的相似性作为度量方法，也不能应用于本文基于DTW的相似连接任务。 最近，为了提高处理时序数据上相似搜索的效率，近似的时序数据表示方法被相继提出。最直接的表示方法是将时序数据切成片段并使用每段中的平均值代表每一个片段。例如，PAA将时序数据均匀切片[42]，也有其他方法采用自适应的切片方式[43]。此外，还有部分工作采用将时序数据进行离散傅里叶变换，奇异值分解或离散小波变换进行表示的方法[44,45]。最新的工作使用基于集合的方法表示时序数据[46]。这些方法在数据类型和相似性度量方式上均与本文有较大区别。 4  相似连接查询处理 本文基于DTW上下界的计算统一处理基于阈值和基于Top-k 的两种时序数据上的相似连接问题。4.1 节首先介绍DTW上下界在两种相似连接问题中的应用，4.2和4.3 节分别介绍本文提出的DTW上界和下界计算方法和相应参数的设置方法。 4.1  基于DTW上下界的相似连接 本节介绍两种相似连接任务如何利用DTW上下界减少计算数据对间的准确DTW。 在基于阈值的相似连接中，算法1利用以下两个事实减少了准确DTW相似度的计算。如果时序数据iT和jT的DTW上界小于给定阈值，无需计算它们的DTW相似度就可以知道它们属于相似连接结果集合(第3-4行)；如果它们的DTW下界大于给定阈值，无需计算它们的DTW相似度就可以知道它们不属于相似连接结果集合(第5-6行)。 在基于Top-k的相似连接中，算法2利用以下两个事实减少了准确DTW相似度的计算： 针对任意时序数据1S TpÎ，如果另一个时序数据pT与qT的DTW相似度的下界大于其它k个时序数据与qT间DTW相似度的上界，pT一定不会存在于qT的Top-k相似连接结果中(第7-8行)；否则，如果pT与qT的DTW相似度的上界小于k个时序数据中的一个时序数据eT与qT的DTW相似度下界，则eT一定不会存在于qT的Top-k 相似连接结果中(第11-16行)。 算法1  基于阈值的相似连接算法 输入  :  时序数据集合1S,2S,  阈值q 输出  :  连接结果时序数据对的集合 ret 1:   f = ret 2:  For each 1S TiÎ   3:            For each 2S TjÎ 4:                    If(q £ ) , (j i UBT T DTW) 5:                           )} , {(j i T T ret ret U = 6:                    Else If (q > ) , (j i LBT T DTW) 7:                            continue 8:                    Else If (q £ ) , (j iT T DTW) 9:                           )} , {(j i T T ret ret U = 10:                 End If 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  7  11:          End For 12: End For 13: return ret 算法2  基于Top-k的相似连接算法 输入  :  时序数据集合1S,2S,  整数k 输出  :  连接结果时序数据对的集合 ret 1:  f = ret 2:    For each 1S TqÎ 3:           f = H 4:            For each 2S TqÎ 5:                   If (k H <) 6:                           } {pT H H U = 7:                  Else If () , (q p LBT T DTW> ) , ' ( max'q UBH tT t DTWÎ 8:                            continue 9:                  Else 10:                         } {pT H H U =   11:                 End If 12:                 While (k H >) 13:                         eT= ) , ' ( max arg'q LBH tT t DTWÎ   14:                      If () , (q p UBT T DTW<) , (q e LBT T DTW) 15:                                 } {eT H H - = 16:                         Else 17:                                  break 18:                         End If 19:                 End While 20:         End For 21:          For each H TpÎ 22:              calculate ) , (q pT T DTW   23:         End For 24:        sort H  by DTW in ascending order 25:        }) { ] 1 : 0 [ (q T k H ret ret ´ - = U 26: End For 27: return ret 4.2 基于DTW的上界计算 我们看到，上述两个算法均需要快速计算时序数据iT和jT的DTW的上界。我们提出基于划分的DTW上界计算方法。具体地，我们将iT和jT分别平均切成1g份，并依次计算iT的第k份] [k Ti与jT的第k份] [k Tj之间的准确DTW。如图3(c)所示，1T和3T被切成均等的1g=2份，得到1T和3T的子序列] 0 [1T，] 1 [1T，] 0 [3T和] 1 [3T。其中] 0 [1T和] 1 [1T之间以及] 0 [3T和] 1 [3T之间的DTW距离分别按图3(c)中左下角和右上角的正方形所示计算。我们可以看到，由于分割后] 0 [1T中后三个时序数据121,103和131无法像图2(b)中那样与] 1 [3T中的前三个时序数据121,103和131匹配，分割后两对子序列的DTW之和相比1T和3T间的准确DTW增加了6对标记为绿色的具有较大差异的数值间的欧氏距离。下面的定理1证明了这样得到的子序列DTW之和是完整序列的DTW上界。 定理1.    给定时序数据iT和jT，如果将它们均匀分割成1g份，则å=£10]) [ ], [ ( ) , (ggj i j ig T g T DTW T T DTW。 证明. iT和jT划分得到的各个子序列依次计算DTW时形成的匹配可以形成iT和jT上进行匹配的一个路径，而它们的DTW之和正是这个路径对应的欧式距离之和。由于DTW(iT,jT)被定义为iT和jT上所有匹配形成路径对应的最小欧式距离，定理1得证。                                                  ■ 由于时序数据被划分成1g份，每一份计算DTW的时间复杂度为O(21) ( g n)，1g个DTW的和所需时间复杂度为O(21) ( g n×1g)=O(12g n)。因此，通过增加划分份数，我们可以成倍减少计算时间。 较大的1g会有较好的加速效果，但DTW计算的任务启动开销增加，计算每对子序列上DTW所占的比重也增加，并且会导致每份子序列较短，引起序列间隔附近的时序数据无法匹配而增大DTW上界与真实值的偏差，进而减弱相似连接的裁剪效果。为了权衡任务启动开销的时间，运行时间和加速效果，我们采用如下方法确定1g：假设任务的启动时间是st，系统计算一个欧式距离的时间是ct，我们首先要求每个任务中进行DTW计算的时间多于任务的启动时间，则每个子时间序列长度至少是c st t /。这样，初始的1g=c st t /。为了避免过大的1g造成DTW上界与真实值偏差过大，我们开始不断迭代计算1g=1g÷2的情况。因为1g较大时运行速度很快，我们可以得到DTW上界随运行时间增加而减少的曲线，当减少速度下降时，即曲线的二阶导数非正时，迭代停止。 4.3 基于DTW的下界计算 8  计  算  机  学  报  2017年 现有的紧的DTW下界计算方法[12]需要对每条时序数据进行所需空间为O(2n)的预处理，远远超出整个数据集大小，因此只适用于查询序列较短且较少的DTW相似查询；其它常用的DTW下界计算方法假设两条时序数据的最大值不同。如图1 所示，这种方法在1T,2T和3T的最大值相同时得到的DTW下界为0，没有效果。 为了克服现有方法存在的缺陷，我们考虑两条时序数据在数值分布上的差异，而不仅仅考虑时序数据对最大值间的差异。具体地，我们用等宽直方图刻画时序数据的数值分布，将时序数据的值域划分成2g个区间，并统计每条时序数据在每个区间上的频数。表2显示了当2g=4时，时序数据1T，2T和3T的值域(0,800]被等宽直方图均匀划分为(0,100], (200,300],(500,600]和(700,800]这4个区间。其中1T和3T都只在(0,100]和(700,800]这两个区间上具有数值分布，而2T则在(200,300],(500,600]和(700,800]这三个数值范围具有数值分布。 为了计算DTW下界，我们假设相同区间内的时序数据都可以匹配且差异为0，不同区间之间如果进行匹配则按距离最近的端点计算距离。这样，1T和3T之间在分布上的差异为0，而2T在(200,300]这个区间里的7 个数值只能和1T和3T的距离(200,300] 最近的(0,100]中的数值进行匹配以取得可能的最小差异。这样，当2T在(200,300]中的数值都取为200，1T和3T在(0,100]中的数值都取为100时，我们得到最少的DTW差异为7×(200-100)。类似地，2T在(500,600]这个区间里的6 个数值为了取得最小差异只能与它最接近的1T和3T的(700,800]区间中的数据进行匹配，差异最小是6×(700-600)。这样，我们可以看到，尽管三个时序数据的最大值相同，他们的DTW下限是不同的。 算法3 描述了这个计算方法。首先，全部时序数据的取值范围被等分为2g份(第1-3行)，并分别计算每条时序数据落在每个区间中的数值的个数(第4-7行)。对于任意时序数据iT和jT，我们针对iT的每个区间，首先使用二分查找寻找jT的区间比这个区间小和大的最接近的非空区间(第9-11行)。若jT中存在相同的非空区间，则下界不增加(第12-13行)，否则选择距离最近的区间计算差值并加入下界(第14-19行)。抛去预计算时划分区间的时间，算法3计算DTW下界复杂度是O(2 2logg g m +)。下面的定理2证明这样得到了DTW(iT,jT)的一个下界。 表2 设备1、设备2和设备3在数值上的分布 设备/区间  (0,100]  (200,300]  (500,600]  (700,800] 设备1(1T)  7      7 设备2(2T)  0  7  6  1 设备3(3T)  7      7 定理2.    给定时序数据iT,jT，将它们的取值等分为2g份，则算法3得到的距离之和不大于( ) ,ij DTW T T。 证明.  对于iT中的任意数值a，假设在DTW中它与jT中的数值b进行匹配，假设a与b落在算法3得到的相同的区间中，则它们的距离被计算为20 ( ) ab £-.假设a与b落在不同的区间12 [ , ] II,34 [ , ] II中，，则算法3中它们的距离为234 ( ) ( ) I I a b - £ -。注意到不等号左侧为算法3得到的距离，右侧为DTW得到的距离，我们知道累加左侧算法3得到的距离不大于累加右侧DTW得到的距离。定理2得证。    ■ 算法3  动态时间规整下界算法 输入  :  时间序列iT和jT,整数2g 输出  : iT和jT的下界 1:  ]} [ ], [ { max max k T k Tj i k = 2:  ]} [ ], [ { min min k T k Tj i k = 3:  2 min) (max g gap - = 4:    For each i iT k T Î ] [ 5:           + + - ] min) ] [ ( [ gap k T Di i 6:   End For 7:  For each j jT k T Î ] [ 8:           + + - ] min) ] [ ( [ gap k T Dj j   9:  EndFor 10: 0 ) , ( =j i LBT T DTW 11: For each 0 ] [ > k D 12:         ] [less jk D=bSearchLargest(jD,left ik D ] [) 13:         ] [more jk D=bSearchLeast(jD,right ik D ] [) 14:          If (left less jk D ] [==] [more ik D) 15:                  continue 16:         End If 16:         left j left i gap k D k D left ] [ ] [ - = 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  9  17:         right i left more j gap k D k D right ] [ ] [ - = 18:          If (gapleft>gapright) 19:                 ) , (j i LBT T DTW= ] [k Di×2gapright 20:        Else 21:                 ) , (j i LBT T DTW= ] [k Di×2gapleft 22:         End If 23: End For 24: return ) , (j i LBT T DTW 较小的2g将使得实际差异较大的数值落在一个区间中进而得到与真实值相差更大的DTW下界，进而减弱相似连接的裁剪效果；由于计算DTW下界复杂度是O(2 2logg g m +)，较大的2g会导致区间数增加，增加DTW下界的计算时间，减少分组开销m所占比重。为了权衡DTW下界计算时间，分组开销和裁剪效果，我们采用如下方法确定2g：假设对每个时序数据中的元素进行分组开销是ot，分组后每组计算时间是ct，则2g应该满足2 2logg g t mtc o £。注意到等号右边随2g的增加而单调增加，我们令2g的初始值为1，然后使用二分法高效地得到最大的整数2g使得不等式成立。得到2g的初始值使得分组代价较小后，我们开始不断迭代计算2g=2×2g的情况。因为2g较小时运行速度很快，我们可以得到DTW下界随运行时间增加而减少的曲线，当减少速度下降时，即曲线的二阶导数非正时，迭代停止。 4.4 扩展到MapReduce框架 由于相似连接仍然涉及双重循环计算，当数据量较大，查询处理依然需要较多时间时，我们可以将上下界计算框架在分布式计算框架MapReduce下实现。当数据被存储在分布式文件系统，如HDFS，中以后，我们只需要一个MapReduce任务进行一轮计算就可以得到相似连接查询结果。在一轮MapReduce计算中，每个map任务负责找到一条时序数据的相似连接结果。例如，每条时序数据1S TiÎ被分配给一个map 任务，这个map任务从分布式文件系统中得到S2的所有时序数据，并使用算法1第3行到第11行的处理过程得到iT的基于阈值的相似连接结果，或使用算法2第3行到第22行的处理过程得到iT的基于Top-k的相似连接结果。这些连接结果是时序数据对<iT,jT>的集合。我们将每个map任务得到的数据对<iT,jT>按照i和j的字典顺序组成键值映射到reduce任务，这样等价的时序数据对会被映射到同一个reduce任务。例如，如果<iT,jT>是相似连接结果，那么负责iT的map任务和负责jT的map任务会产生两个重复的相似连接结果，而这两个重复的结果由于具有相同的键值会被映射到一个reduce任务中，这样reduce任务去掉重复的查询结果后就得到了整个查询的结果。这样基于并行计算框架MapReduce的解决方案扩展了我们的方法在大数据领域的应用。 5  实验 本节中我们同时使用真实和合成数据验证本文方法的性能与效果。实验说明了下述问题：(1)基于DTW的时间序列相似度连接在相关性分析和双语名词匹配方面的实际应用；(2)本文提出的相似连接算法与上下界计算方法是有效的。 5.1实验环境与数据集描述 我们使用C++实现本文方法，实验环境是一台Linux服务器，英特尔至强E5645 2.4Ghz处理器，8G内存，1T SATA硬盘。我们实现了原本的DTW算法[5]、广泛应用的高效近似DTW计算方法FastDTW[17]、广泛应用的DTW下界高效计算方法Kim下界[11]和Yi下界[12]以及当前效果最好的Keogh下界[13]。 我们使用两个真实数据集以及合成数据集。第一个真实数据集包含某地电力部门10年的配电设备每15分钟采集一次的实时功率，这样一共具有时间序列103条，其中每条的长度均经过分词后，我们统计每个词汇依次出现在每100个词汇中的频率。这两个数据集分别包含了较长的时间序列和较短的时间序列。合成数据生成不同长度的时间序列，并采用正态分布生成方差在(0,1]内随机取值的时序数据用于相似连接的性能测评。各数据集的时间序列长度和个数情况见表3。   表3  数据集 数据集  时间序列长度  时间序列个数 配电网  350400  103 英文文本  7500  2000 中文文本  5700  2000 合成数据  103-106  102-104 5.2基于DTW相似连接的实际应用 10  计  算  机  学  报  2017年 配电网数据集除包含各配电设备的输电功率时序数据外，还提供了各配电设备所处区域的信息。图4用相同的颜色显示了两个不同区域间的供电设备在时序数据正规化到[0,1]区间内，阈值5 = q时相似连接下的匹配情况。我们可以看出，处于各集镇中心区域的供电设备被连接到一起，这揭示了这些区域的供电设备具有相同的功率变化趋势，例如在工作日白天输电功率上升，夜晚输电功率下降等。利用DTW相似连接的结果，匹配在一起的供电设备的输电功率产生较大差异往往意味着输电线路出现异常，并触发电力公司的输电线路异常预警。 县变压器碧峰寺碧峰寺抽水八里庄中心何家槽中心何家槽新增姚家崖中心 图4 配电网数据集在5 = q时的相似连接结果 在第二份文本数据中，图2显示了英文的“God”一词和中文的“上帝”一词在每依次100个词中出现的频率的变化情况。表4显示了8个Top-1相似度的匹配结果。可以看出，“上帝”和“God”等不同语言下具有相同含义的名词实体很容易地被自动连接起来，这为双语实体匹配等任务提供了便利。 5.3性能比较 图5 分别显示了配电数据集和文本数据集上现有方法完成任务所需的时间。对比图5(a)和图5(b)，我们可以看出，虽然文本数据集下时间序列的个数是电网数据集下时间序列个数的20倍，即不经过裁剪时需要比电网数据集多计算近400倍的DTW准确值，文本数据集下相似连接所需的运行时间依然不到电网数据集下的六十分之一。这是因为文本数据集中时序数据相对较短，而DTW计算时间是时序数据长度的三次方函数，而需要比较的时序数据对数是时序数据个数的二次方程函数。这验证了我们使用DTW上下界裁剪需要计算DTW的数据对的合理性。 表4  Rest数据集上的准确性比较 英文词汇  中文词汇  英文词汇  中文词汇 God  上帝  People  人们 Father  父亲  King  王 House  房屋  Israel  以色列 Say  说  Land  陆地 另一方面，我们可以看出，SJ，SJ_yi和SJ_kim所需时间都小于基于FastDTW和DTW的方法。这是因为DTW和FastDTW不能避免对全部数据对进行相似度的计算，而前三种针对相似连接的方法尽管对需要计算DTW的数据对裁剪比例不同，但都大规模减少了DTW的计算。特别地，本文方法在两个数据集中一致地比最新的方法快接近一个数量级以上。特别值得注意的是，目前最好的DTW下界Keogh下界的运行时间是最慢的，比原始DTW方法还慢近一倍。这是因为Keogh下界需要对每条曲线进行空间复杂性为O(2n)的处理。在以后的实验中除非特殊说明，我们不包括Keogh下界的结果。 图6 显示了合成数据集中不同长度的时间序列上各个方法的性能对比情况。图6(a)(b)显示了当时序数据长度是102时，各种方法在5 = q和10 = k的效果。我们可以看到因为时序数据较短，DTW的计算很快，各个上下界计算方法并没有数量级上的优势。图6(c)-(f)显示了当时序数据长度是103和104时，各种方法在5 = q和10 = k的效果。我们可以看到当时序数据较长时各种基于计算上下界的方法的优劣和图5(a)类似。  (a)配电网数据集                                      (b)文本数据集 图5 真实数据集上的性能对比 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  11           (a)长度=102时5 = q                 (b)  长度=102时10 = k      (c)长度=103时5 = q                   (d) 长度=103时10 = k  (e)长度=104时5 = q                           (f) 长度=104时10 = k 图6 不同时序数据长度下的性能对比 图7显示了不同数据集上调整阈值q后的相似连接运行时间。我们可以看出，当q增加时，由于结果集增大，各种方法的运行时间均有所增加。特别地，Kim下界和Yi下界的运行时间随q增加显著变长，而我们的方法的运行时间增加不明显。这是因为q增加时其他方法由于下界不准确，需要进行验证的候选结果集较大，导致需要计算更多时序数据对的DTW。对比图  7(c)(d)，我们可以看出，当q确定而时序数据个数增加时，本文的SJ方法的运行时间没有显著增加。这是因为本文的下界随着数据集长度的增加显著增加，裁剪掉了更多的时序数据对。 12  计  算  机  学  报  2017年      (a)配电网数据集                                      (b)文本数据集     (c)104条合成时序数据                      (d)102  条合成时序数据 图7 q对相似连接性能的影响    (a)配电网数据集                                                                                  (b)文本数据集 图8 k对相似连接性能的影响 图8显示了不同k值下的Top-k相似连接的运行时间。我们可以看出，当k增加时，我们的Top-k  SJ 方法和基于FastDTW及原始DTW的方法的运行时间没有显著增加，而基于Yi下界和Kim下界的两种方法的运行时间显著增加。一方面，这是因为基于FastDTW和DTW的方法需要对全部数据对求DTW值，因此k的增加并不增加这两种方法的计算量；另一方面，基于Yi下界和Kim下界的两种方法由于k值增大，需要进行DTW计算的候选数据对显著变多，因此增加了验证过程中计算DTW的数据对个数。而我们的方法由于具有高效的上下界计算方法，在k增加时需要计算DTW的数据对个数并没有显著增加，因此运行时间没有随k的增加显著增长。 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  13                   (a)裁剪比例随2g的变化                    (b)裁剪比例随1g的变化                    (c)裁剪比例比较                              (d)上下界计算代价比较 图9 上下界计算效果与代价 5.4  上下界计算效果与性能 我们通过计算被裁剪的数据对占全部数据对比例衡量上下界计算方法的效果。其中，裁剪掉的数据比例越高说明上下界计算效果越好。 图9展示了不同1g和2g对性能的影响，同时用黑色竖线标出了计算DTW上界和下界的迭代结束时得到的1g和2g的位置。在固定1g为时序数据长度的0.01%时，图9(a)显示随着2g的增加，裁剪比例的增加速度在2g大于时序数据长度的0.01%时逐渐变慢。这是因为当2g增加到数据长度的0.01%时，大部分不能匹配的情况已落在不相邻的数据间隔中成为DTW下界的组成部分。当2g继续增加时，新的变化主要体现在较大的数值间隔被拆成相邻的两个数值间隔，这并不能显著增加DTW下界。固定2g为时序数据长度的0.01%时，图9(b)展示，裁减比例在1g小于0.01%时增加缓慢，而在1g大于0.01%时增加迅速。这是因为当1g为时序数据长度的0.01%时，对于不同长度的时序数据，每个时序子序列的长度都在10000左右，再增加子序列的长度得到的上界准确程度的增益有限。同时，我们可以看到迭代结束时得到的1g和2g具有较高的裁剪比例。 图9(c)显示了1g和2g为时序数据长度的0.01%时，我们的方法与最新方法Keogh下界以及常用的Yi下界和Kim下界效果的比较。结果显示，和已被证明是紧的下界Keogh下界相比，本文提出的方法的裁剪比例与其相当。此外，本文方法的裁剪比例是其他两种方法的3倍以上。图9(d)验证了我们的上下界计算方法是高效的：我们的方法和Kim下界的计算代价相当，远小于Yi下界和Keogh下界的计算代价。 6  结束语 本文提出了时间序列数据上一种新的查询类型：基于DTW的相似连接。这种查询可以为时间序列上的数据挖掘任务(如跨语言词汇匹配、相关性分析等)提供重要的数据处理结果。本文还首次定义了基于阈值和基于Top-k 这两种新颖的DTW相似连接任务。为了提高查询处理效率，本文分别提出了时间序列间的DTW上界和下界计算方法。本文在真实的配电网数据以及本文数据上验证了本文提出的两种DTW相似连接任务在实际中的应用，并进行了充分的实验证明本文提出的基于DTW的相似连接方法和DTW上下界计算方法是高效的。 本文的相似连接涉及两重循环计算，对大数据而言计算复14  计  算  机  学  报  2017年 杂度仍然偏大。我们将在后续工作中关注如何支持某种索引机制，利用前缀过滤、分段过滤等字符串相似连接技术取得更高的裁剪效果，进一步加快大数据集下的连接操作。  致  谢  审稿专家和编辑老师提出了宝贵的修改意见和建议，在此表示衷心的感谢！   参 考 文 献 [1] Thanawin R, Bilson C, Abdullah M et al. Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, Beijing, China,2012: 262-270 [2] Nurjahan Begum, Eamonn J. Keogh. Rare Time Series Motif Discovery from Unbounded Streams. Proceedings of the VLDB Endowment, 2014, 8(2):149-160 [3] François P, Germain F, Geoffrey I et al. Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification. Proceedings of the IEEE International Conference on Data Engineering, Shenzhen, China, 2014: 470-479 [4] Thanawin Rakthanmanon, Eamonn J. Keogh. Data Mining a Trillion Time Series Subsequences Under Dynamic Time Warping. Proceedings of the Twenty-Third international joint conference on Artificial Intelligence. Beijing, China, 2013: 3047-3051 [5] Sakoe H, Chiba S. Dynamic programming algorithm optimization for spoken word recognition. Readings in speech recognition. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. 1990: 159-165  [6] Keogh E. Kasetty S. On the need for time series data mining benchmarks: a survey and empirical demonstrations. Proceedings of the 8th International Conference on Knowledge Discovery and Data Mining, Edmonton, Canada, 2003:349-371 [7] Chotirat (Ann) Ratanamahatana, Eamonn J. Keogh. Three Myths about Dynamic Time Warping Data Mining. Proceedings of the SIAM International Conference on Data Mining. Houston, Texas, USA. 2005: 506-510 [8] Adams N, Marquez D, Wakefield G. Iterative deepening for melody alignment and retrieval. Proceedings of the 6th International Conference on Music Information Retrieval. London, UK, 2005: 199-206 [9] Chuitian R, Wei L, Xiaoli W et al.. Efficient and Scalable Processing of String Similarity Join. IEEE Transactions on Knowledge and Data Engineering.2013, 25(10):2217-2230 [10] Pang Jun,Gu Yu,Xu Jia,Yu ge. Research Progress on similarity join query technology. Computer science and exploration.2013, 7(1): 1-13. (in Chinese) (庞俊,谷峪,许嘉,于戈.  相似性连接查询技术研究进展.  计算机科学与探索, 2013, 7(1): 1-13.) [11] Kim S, Park S, Chu W. An index-based approach for similarity search supporting time warping in large sequence databases. Proceedings of the 17th International Conference on Data Engineering. Washington, USA, 2001:607-614 [12] Yi B, Jagadish K, Faloutsos H. Efficient retrieval of similar time sequences under time warping. Proceedings of the Fourteenth International Conference on Data Engineering. Orlando, Florida, 1998:201-208 [13] Faloutsos C, Lin K. FastMap: A fast algorithm for indexing of traditional and multimedia datasets. Proceedings of the 1995 ACM SIGMOD international conference on Management of data. California, USA, 1995: 163-174  [14] M. Zhou, M. H. Wong, Boundary-based lower-bound functions for Dynamic Time Warping and their indexing. Information Sciences,2001, 181(19): 4175-4196.   [15] Lemire, D. Faster Retrieval with a Two-Pass Dynamic- Time-Warping Lower Bound. Pattern Recognition 2009, 42(9):2169-2180 [16] A. Fu, E. Keogh, L. Lau et al. Scaling and time warping in time series querying. The VLDB Journal , 2008, 17(4):899-921 [17] Sakurai, Y., Yoshikawa, M., and Faloutsos, C. FTW: Fast Similarity Search under the Time Warping. Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, New York, USA,2005: 326-337 . [18] Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. Proceedings of the 2003 ACM SIGMOD international conference on Management of data, California, USA, 2003 : 181-192  [19] P. Papapetrou, V. Athitsos, M. Potamias et al. Embedding-based subsequence matching in time-series databases. Acm Transactions on Database Systems, 2011, 36(3):1-39 [20] H.R. Lee, C. Chen, J. R.Jang. Approximate lower-bounding functions for the speedup of DTW for melody recognition Proceedings of the 9th IEEE International Workshop on Cellular Neural Networks and their Applications. Taoyuan,China, 2005:178-181 [21] Panagiotis P, Paul D, Vassilis A. Towards faster activity search using embedding-based subsequence matching, Proceedings of the 2nd International Conference on Pervasive Technologies Related to Assistive Environments. Corfu, Greece, 2009:1-8 [22] Vassilis A, Panagiotis P, Michalis P et al. Approximate embedding based subsequence matching of time series. Proceedings of the 2008 ACM SIGMOD international conference on Management of data. Vancouver, Canada, 2008: 365-378 [23] C. Xiao, W. Wang, X. Lin, and J. X. Yu. Efficient similarity joins for near duplicate detection. In International Proceedings of the 17th international conference on World Wide Web, Beijing, China, 2008:131-140 [24] J. Wang, G. Li, and J. Feng. Can we beat the prefix filtering?: an adaptive framework for similarity join and search. Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, Scottsdale, Arizona, USA, 2012: 85-96  [25] S. Sarawagi and A. Kirpal. Efficient set joins on similarity predicates. In ACM Conference on Management of Data Conference, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, Paris, France, 2004: 743-754 [26] A. Arasu, V. Ganti, and R. Kaushik. Efficient exact set-similarity joins. Proceedings of the 32nd international conference on Very large data bases. Seoul, Korea, 2006:918-929 [27] C. Xiao, W. Wang, X. Lin, and H. Shang. Top-k set similarity joins. Proceedings of the 25th International Conference on Data Engineering. Shanghai, China, 2009:916-927 [28] R. Vernica, M. J. Carey, and C. Li. Efficient parallel set-similarity joins using mapreduce. Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. Indianapolis, Indiana, USA, 论文在线出版号  No.47  周宁南等：基于动态时间规整的时序数据相似连接  15  2010:495-506 [29] D. Deng, G. Li, S. Hao, J. Wang, and J. Feng. Massjoin: A mapreduce-based method for scalable string similarity joins. Proceedings of the 2014 IEEE 30th International Conference on Data Engineering. Chicago, USA 2014:340-351 [30] Yu J, Guoliang L, Jianhua F. String Similarity Joins: An Experimental Evaluation. Proceedings of the Vldb Endowment, 2014, 7(8):625-636 [31] Gravano, L., Ipeirotis, P.G., Jagadish, H.V., Koudas, N., Muthukrishnan, S., Srivastava, D.: Approximate string joins in a database (almost) for free. Proceedings of the 27th International Conference on Very Large Data Bases. San Francisco, USA , 2001:491–500  [32] Chaudhuri, S., Ganti, V., Kaushik, R.: A primitive operator for similarity joins in data cleaning.  Proceedings of the 22nd International Conference on Data Engineering , Washington, USA , 2006:5–16 [33] Arasu, A., Chaudhuri, S., Kaushik, R.: Transformation-based framework for record matching. Proceedings of the 24th International Conference on Data Engineering. Cancun, Mexico. 2008:40-49 [34] R. J. Bayardo, Y. Ma, and R. Srikant. Scaling up all pairs similarity search. In International. Proceedings of   the 16th international conference on World Wide Web, Banff, Canada 2007:131-140 [35] Jin W, Guoliang L, Dong D et al. Two Birds With One Stone: An Efficient Hierarchical Framework for Top-k and Threshold-based String Similarity Search.Proceedings of the IEEE International Conference on Data Engineering, Seoul, Korea,   2015:519-530 [36] Dong D, Guoliang L, Jianhua F. A Pivotal Prefix Based Filtering Algorithm for String Similarity Search. Proceedings of the ACM Conference on Management of Data, Snowbird, USA, 2014:673-684 [37] T. Brinkhoff, H.-P. Kriegel, and B. Seeger. Efficient Processing of Spatial Joins Using R-Trees. Proceedings of the 1993 ACM SIGMOD international conference on Management of data. Washington, USA, 1993: 237-246 [38] Y.W. Huang, N. Jing, and E.A. Rundensteiner, Spatial Joins Using R-Trees: Breadth-First Traversal with Global Optimizations. Proceedings of the 23rd International Conference on Very Large Data Bases, San Francisco, USA, 1997: 396-405  [39] M.L. Lo and C.V. Ravishankar, Spatial Hash-Joins. ACM Conference on Management of Data. 1996, 25(2):247-258 [40] Xiang Lian, Lei Chen. Efficient Similarity Join over Multiple Stream Time Series. IEEE Transactions on Knowledge and Data Engineering 2009, 21(11):1544-1558 [41] Xiang Z, Chuan X, Xuemin L et al. Efficient Graph Similarity Joins with Edit Distance Constraints. Proceedings of the 2012 IEEE 28th International Conference on Data Engineering, Washington, USA: 834-845 [42] E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. Knowledge and Information Systems, 2001, 3(3):263-286 [43] E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Locally adaptive dimensionality reduction for indexing large time series databases. ACM Transactions on Database Systems, 2002, 27(2): 188-228  [44] C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. Proceedings of the 1994 ACM SIGMOD international conference on Management of data. Minneapolis, Minnesota, USA, 1994: 419-429  [45] Z. R. Struzik and A. Siebes. Wavelet transform in similarity paradigm. Lecture Notes in Computer Science (LNCS). Berlin,Germany: Springer, 1998:295-309 [46] Jinglin Peng, Hongzhi Wang, Jianzhong Li, and Hong Gao. 2016. Set-based Similarity Search for Time Series. Proceedings of the 2016 International Conference on Management of Data. San Francisco, USA, 2016:2039-2052 16  计  算  机  学  报  2017年 Zhou  Ningnan,  born  in  1990 ，PhD candidate.  His  research  interests  include database  system  and  data  mining. Zhang Xiao,  born  in  1972,  PhD,  associate  professor.  His research interests include database and big data research.   Liu Chengshan，born  in  1992,  Master  candidate.  His research interests focus on database.  Wang Shan,  born  in  1944,  M.S.,  professor.  Her  research interests  include  database  systems, data  warehouse,  DB-IR, main memory database and big data research. Background    Time  series  data  is  pervasive  across  almost  all  human endeavors,  including  medicine,  finance,  science  and entertainment. As such, it is hardly surprising that time series data  mining  has  attracted  significant  attention  and  research effort.  Most  time  series  data  mining  algorithms  require similarity  join  as  a  subroutine,  and  in  spite  of  the consideration  of  dozens  of  alternatives,  there  is  increasing evidence  that  the  classic  Dynamic  Time  Warping  (DTW) measure is the best measure in most domains. Currently,  due  to  the  high computationally complexity of DTW, none works has considered the proposed problem in this  paper,  namely  the  similarity  join  on  time  series  under DTW.  Works  on  DTW  suffers  from  high  pre-computation overhead  when  they  are  applied  to  similarity  join  while works  on  similarity  join  has  not  considered  the  DTW measure. This paper for the first time defines and investigates the  novel  problem  of  similarity  join  on  time  series  under DTW  measure  and  develops  two  novel  upper  and  lower bounds  on  DTW  to  speed  up  the  query  evaluation.  Real world  datasets  demonstrate  the  applications  of  our  proposed problem  and  extensive  experiments  on  real  world  and synthetic  datasets  validate  the  effectiveness  of  our  solution and  the  pruning  power  of  our  proposed  upper  and  lower bounds. The  work  is partially supported  by supported  by  the State  Key  Program  of  National  Natural  Science  of  China (Grant  No. 61432006). This  work  is  partially  supported  by National  Key  Research  and  Development  Program  (Project Number: 2016YFB1000700).