2019, Vol. 45
, 2. 海军军医大学 研究生四大队, 上海 200433;
3. 江南计算技术研究所, 江苏 无锡 214081;
4. 复旦大学 计算机学院, 上海 201203
2. Forth Team of Postgraduates, Naval Medical University, Shanghai 200433, China;
3. Jiangnan Institute of Computing Technology, Wuxi, Jiangsu 214081, China;
4. School of Computer Science, Fudan University, Shanghai 201203, China
时间序列的分析与挖掘是数据分析领域一个重要的研究方向。海量时间序列具有规模大、维度高和特征多样化的特点, 对索引提出了更高的划分精度要求。由于时间序列都具有较高的维度, 直接在原始数据上进行处理的代价较大, 因此可对时间序列数据进行数据或维度的规约和变换, 将数据映射到变换后的空间中, 并保留一小组“最强”变换后的系数作为特征。目前, 在海量时间序列上进行批量查询的应用越来越多, 其中一个典型的应用是在物联网中对多个传感器采集的数据进行批量查询。现有主流的时间序列索引技术, 如DSTree[1]、iSAX[2]等都不是平衡树, 而树状索引不具备平衡性导致索引对某些具有特殊分布的时间序列的查询性能较差。此外, 海量时间序列需要分布式且具有良好平衡性和局部性的索引, 而时间序列索引的非平衡性会影响其分布式实现的性能。
MapReduce[3]计算模型是目前云计算环境下最流行的分布式计算模型之一, 它可以将计算均匀地分布在多台异构计算机上, 并且屏蔽了复杂的并行编程, 使得并行应用可以归结为2个简单的函数, 即Map函数和Reduce函数。MapReduce模型的高可用性、高可扩展性、高容错性和简单性使其受到高度重视。一些著名的IT公司, 如Facebook、雅虎等均采用Hadoop的MapReduce模型作为云计算环境中的重要基础软件。
本文提出一种基于MapReduce的批量查询方法。在Hadoop上构建分布式且具有平衡性的DSTree索引(Distributed and Balanced DSTree, DB-DSTree)。该索引采用双层树结构, 其顶层树结构是一棵建立在采样的原始时间序列上的平衡DHD树[4], 时间序列以DHD树作为路由进行分区, 底层是在路由到各分区的时间序列上建立的DSTree树。在此基础上, 利用DB-DSTree进行批量查询, 并根据路由树对查询进行分组, 每组查询对应不同的子树。在每个Reducer上维护一个缓存, 已经读取的DSTree叶子文件保存在该缓存中, 避免频繁读取Hodoop分布式文件系统(HDFS)中保存的数据, 从而提高查询效率。
1 预备知识与相关工作 1.1 预备知识 1.1.1 时间序列相似性查询定义1 时间序列是指按时间顺序排列、具有相等时间间隔的一系列观测数据的集合, 记为:
| $ S=\left(s_{1}, s_{2}, \cdots, s_{i}, \cdots, s_{n}\right), 1<i<n $ | (1) |
其中, si为在时刻i观测到的数据, n为时间序列的长度。给定一个时间序列集合S和序列q, 其精确查询和批量查询的具体定义如定义2、定义3所示。
定义2 时间序列的精确查询是指返回序列t∈S, 满足:
| $ \forall t^{\prime} \in S, d(q, t) \leqslant d\left(q, t^{\prime}\right) $ | (2) |
定义3 时间序列的批量查询是指对于一个时间序列的集合Q, 其中的每一个时间序列q的返回序列t∈S, 满足:
| $ \forall t^{\prime} \in S, d(q, t) \leqslant d\left(q, t^{\prime}\right) $ | (3) |
降维表示与时间序列集合的整体特征无关, 仅与待处理的时间序列本身有关。常用的时间序列降维技术有:离散小波变换(Discrete Wavelets Transform, DWT)[5], 离散傅立叶变换(Discrete Fourier Tranforms, DFT)[6], 符号近似聚合(Symbolic Aggregate approximation, SAX)[7], 奇异值分解(Singular Value Decomposition, SVD)[8], 适应性分段常数近似(Adaptive Piecewise Constant Approximation, APCA)[9], 分段累计近似(Piecewise Aggregate Approximation, PAA)[10], 分段线性近似(Piecewise Linear Approximation, PLA)[11]等。图 1给出其中6种降维技术的示意图。在图 1中, 上半部分是时间序列数据的示意图, 下半部分给出时间序列数据降维后的数段表示。
|
Download:
|
| 图 1 时间序列降维技术示意图 | |
维度层次分解索引本质上是k-d树在时间序列数据上的扩展, 如图 2所示。在节点分裂过程中, 采用多个维度的组合作为数据划分的度量, 而不是只选择一个维度来进行数据划分, 以有效缓解维度灾难带来的数据划分问题。DHD索引在保存k-d树的平衡树特征的同时, 通过一种动态的维度组合策略来保证数据划分的度量具有较好的区分度。DHD索引是一种树状索引, 可以将相似的时间序列数据快速分配到DHD索引树的叶子节点中。需要注意的是, 对于高维的时间序列, 采用传统的R树、k-d树索引会使其受到维度灾难的影响, 无法达到理想的数据划分效果。DHD索引通过结合降维和建立索引的过程, 减少建立索引过程中的计算量, 同时缓解维度灾难对于时间序列数据划分的影响。
|
Download:
|
| 图 2 DHD结构 | |
DSTree是一个具有数据适应性的针对时间序列数据的动态分段索引。该索引可被用来执行有效的时间序列查询, 提供一个时间序列到一组时间序列的紧致的上下界估计。DSTree采用一种扩展的APCA表示EAPCA, 即采用时间序列的每个分段来计算标准差, 并将其加入到APCA表示中。
1.2 相关工作时间序列相似性查询是时间序列挖掘领域的一个重要研究方向[12-14]。相似性查询是指在一个时间序列数据集上, 根据某种相似性度量函数, 寻找与给定时间序列最相似的目标序列集合, 其可分为全序列匹配和子序列匹配2大类[15]。其中, 全序列匹配是指查找的时间序列与目标序列具有相同的长度, 而子序列匹配则是指在一个更长的序列中, 找出与目标序列相似的所有子序列。
常见的时间序列的度量包括欧几里得距离(Euclidean Distance, ED)和动态时间扭曲距离(Dynamic Time Warping, DTW)[16]。虽然对于大多数数据挖掘任务而言, DTW的准确率高于ED, 但是随着数据集规模的扩大, ED的错误率会收敛至DTW的错误率。由于ED的处理速度远高于DTW且基于ED的索引较容易转化为基于DTW的索引, 因此时间序列的索引可以基于ED进行度量。在基于DTW的时间序列索引工作中还包括NLB-FDTW[17], 这是一种改进的基于下界函数的DTW。
提高时间序列的相似性查询性能最重要的方法之一是建立时间序列的索引, 直接在原始的时间序列上建立索引代价太高, 因此需要先进行降维处理。时间序列的降维表示技术包括DFT、PLA、SVD、DWT、分段常量近似(Piecewise Constant Approximation, PCA)、APCA、PAA、SAX及其扩展索引符号累计近似(indexable SAX, iSAX)。iSAX通过多分辨率的SAX表示将时间序列组织成一棵树状索引, 每一个节点对应一个SAX的前缀表示, 在节点分裂时, 选择最能将数据分开的分段。iSAX 2.0[18]和iSAX 2+[19]是2种基于iSAX的优化方法, 其相关表示方法还有ADS[20]和COCONUT[21]。
基于SAX表示的分段是等长的分段, 由于DSTree引入了动态分段索引的概念, 各叶子节点的分段可以不一致。以往的时间序列查询工作没有结合大数据计算平台, 为充分利用大数据平台的计算和存储优势, 本文提出基于MapReduce的DB-DSTree索引, 以提高海量时间序列的查询性能。
2 基于MapReduce的DB-DSTree索引对于海量时间序列, 单机的索引创建方法远不能满足现实应用的需求。本文提出一种基于MapReduce的分布式DSTree索引的创建与批量查询方法。由于DHD树具有均衡性, 因此对于海量时间序列, 可通过采样建立DHD树并将其作为路由树, 指导MapReduce任务的数据划分。DHD树的均衡性会影响其节点的紧致性, 考虑到DHD树的紧致性不如DSTree树, 因此, 采用DHD树结合DSTree的两层索引方式来实现分布式的MapReduce索引创建和分布式查询。
2.1 基于DHD索引的路由树创建选择DHD索引作为路由树是因为利用DHD索引可以实现如下2个内容:
1) 快速数据划分
DHD索引建立在时间序列数据的基于维度层次分解树的维度组合摘要之上, 而不是直接建立在原始的时间序列上。与利用原始时间序列进行距离比较从而分裂节点的方法相比, 利用维度组合摘要可以节省大量计算代价。
2) 分区大小近似相同且具有数据局部性
在DHD节点中保存原始时间序列的维度组合摘要, 当节点分裂时, 在候选维度组合中选取差异最大的一组, 这里的差异是指方差乘以候选维度的权重。通过一种快速中位数定位方法, 得到维度组合摘要的中位数, 大于该中位数的维度组合摘要保存在右边的节点中, 而小于该中位数的保存在左边的节点中。这种分裂方式可以使得分区具有近似相等的维度组合摘要个数。
本文采用一个MapReduce任务进行路由树创建。在Map阶段, 先根据给定的概率决定该时间序列是否需要采样, 并将需要采样的时间序列转换为DHD表示。在Reduce阶段, 由一个Reduce任务进行DHD索引创建, 并将创建的索引直接保存在Hadoop分布式文件系统上。
2.2 分布式DSTree索引的创建分布式DSTree索引的创建过程如图 3所示。首先, 通过采样生成一棵DHD索引树作为路由树, 然后按照插入方式, 找出数据集中所有时间序列对应路由树的叶子节点。以叶子节点的id作为key值, 以该时间序列为value值, 按照同一个key值聚集起来的时间序列由同一个Reduce函数进行处理, 创建出第2层DSTree树。为避免生成过多的子树, 按照叶子节点的顺序将一定数目的对应连续key值的时间序列路由到一起, 创建子树。路由树保存在HDFS中, 然后在Reduce阶段被初始化到每个Reducer内存中。DHD的叶子节点按照从左到右的顺序进行排列, 每k个叶子节点对应一棵DSTree子树, 从而可以实现k个Reducer同时进行数据插入。将每k个DHD叶子节点的时间序列聚集在一起, 并将其所创建的DSTree子树保存在HDFS上。k的选择与路由树的高度h有关, 由于DHD是一棵平衡树, 其高度h决定了DHD树叶子节点的个数, 例如, 要建立8棵DSTree子树, DHD索引树的高度为6, 一共有32个叶子节点, 则k=32/8=4。
|
Download:
|
| 图 3 DB-DSTree索引创建过程 | |
创建DB-DSTree索引树的伪代码如下:
//创建DHD路由树
Map阶段
key:null, value:a time series
1.for each time series ts
2.do sampling with sample rate β
3.compute DHD representation dhd of ts
4.context.write(1, dhd)
Reduce阶段
5.build DHD index on the DHD representations
6.save DHD index on HDFS
//创建DSTree子树
Map阶段
7.read DHD tree from HDFS to Mapper memory
8.for each time series ts
9.find the leaf node by inserting mode, denoted as lnode
10.subtreeID= lnodeID/k
11.context.write(subtreeID, ts)
Reduce阶段
12.build DSTree index for the time series of each reduce function
13.save DSTree index files and data files on HDFS in cleanup function of reducer
DB-DSTree索引树的创建由2个MapReduce任务组成:
1) 创建DHD路由树。由于DHD树是一棵建立在内存中的平衡树, 并且利用其充当路由树, 因此需要对原始时间序列的数据进行采样, 采样率β由单台机器内存和DHD树的规模决定。在Map阶段, 每一个Map函数的输入 <key, value>为一条时间序列, 并根据采样率决定该时间序列是否被采样, 如果被采样, 则计算其DHD表示。将时间序列的DHD降维表示为不同层次维度组合的均值。在Reduce阶段, 所有被采样时间序列的DHD降维表示被路由到一个Reduce函数中暂存。cleanup()函数在此基础上建立DHD索引树, 并将其保存在HDFS上。当β=1时, 路由树建立在所有时间序列上, 对于数据集内的时间序列, 可以保证路由百分之百的准确率。对于不在数据集内的时间序列, 存在出现在路由导向的子树的相邻子树的概率, 此时可增加相邻子树的查询。当数据集过大时, 由于受内存的限制, β值较小, 而路由的偏差会较大, 对于这种情况, 通过增加查询子树的范围可以提高查询的准确性。
2) 创建DSTree子树。根据路由树对原始时间序列进行分区, 在每个分区上建立一棵DSTree树。在Map阶段, 当Mapper启动时, 通过Mapper的初始化函数setup()将保存在HDFS上的路由树加载到Mapper的内存中, 使得DHD路由树可以被所有Map共享。按照DHD索引树的插入方式, 找到每一条时间序列对应的DHD索引树的叶子节点, 并通过叶子节点的标号lnode确定其所对应的分区, 然后利用分区标识subtreeID对时间序列进行分区。在Reduce阶段, 每一个Reduce函数中的value对应一个分区的时间序列, 在其上建立DSTree并将结果保存在HDFS上。
2.3 批量查询基于DB-DSTree索引进行批量查询主要得益于DB-DSTree良好的平衡性和局部性。DHD索引主要考虑时间序列划分的均衡性, 并可以快速找到近似的时间序列, 但叶子节点的紧致性不如DSTree。在进行批量查询时, 有些查询会频繁访问同一节点, 充分利用DB-DSTree的局部性可有效减少磁盘IO的数量。这是因为精确查找需要找到时间序列集合中与查询时间序列Q距离最近的时间序列, 并检查每个没有过滤掉的叶子节点中的时间序列, 而这些时间序列是以文件形式存储的。
利用DB-DSTree进行批量查询的伪代码如下:
Map阶段
key:null, value:time series ts
1.read DHD index from HDFS to Mapper memory
2.for each time series ts, find the approximate nearest leaf node of DHD tree, compute subtreeID by lnodeID/k
3.context.write (subtreeID, query)
Reduce阶段
key:subtreeId, value:list of queries routed to the DSTree identified by subtreeId
4.for each group of time series
5.read corresponding DStree, denoted as subtreeID from HDFS to Reducer memory
6.recall exact search function on DSTree ds
在Map阶段, 将路由树加载到Mapper的内存中被所有的Map函数共享, 每一个Map函数处理一条查询。对于每一条查询, 在路由树上进行启发式近似查询, 得到路由树上到达的叶子节点, 将该节点标记为lnodeID。根据lnodeID找到对应的子树, 标记为subtreeID。在创建DB-DSTree时, 将路由到每k个DHD树叶子节点的时间序列作为一个单位建立DSTree, 且DHD树叶子节点的排序方式是从左到右, 因此, 查询ts对应的子树为lnodeID/k。对应相同子树的查询被路由到同一个Reduce函数中处理。
在Reduce阶段, 根据subtreeID将子树的索引加载到Reducer的内存中, 其通过调用Reducer的setup()函数实现的。对于每一条查询, 在DSTree树上进行精确查询, 同时在Reducer的内存中维护一个缓存, 避免重复从HDFS中读取数据。上述缓存是一个HashMap表, key为DSTree树的叶子节点对应的存储时间序列的文件名, value为该文件的内容。
在DSTree上执行精确查询的具体步骤如下:
1) 通过近似查找得到一个当前的最优解BSF, 此时的距离为ε。根据DSTree索引节点的下界性质过滤掉下界大于ε的节点, 对于没有过滤掉的节点, 如果其时间序列与查询的时间序列的距离小于ε, 将ε设置为该距离值, 并继续进行下界裁剪。
2) 利用最优解BSF可以裁剪相当大的搜索空间。在得到BSF后, 建立一个查询优先级队列pq, 将所有需要检查的内部节点和叶子节点保存在其中。优先级队列pq中的节点按照其与查询序列Q的距离下界升序排序, 每次取出具有最小下界的节点进行处理, 直到队列为空或者满足d(q, t)=0时, 队列中剩余节点的时间序列与查询时间序列的距离不可能小于BSF, 因此可以安全地被排除。在对节点进行处理时, 有2种情况:
(1) 如果该节点是叶子节点, 读出其对应的时间序列, 并逐个计算真实距离, 得到其中的最小距离。若该距离比当前最优解BSF小, 则更新BSF为该最小距离。
(2) 如果该节点是中间节点, 根据DSTree的时间序列与节点近似表示的下界, 计算查询时间序列与节点中时间序列的下界。如果该下界大于BSF, 将该节点排除, 否则将该中间节点的左右子节点加入队列中。
3 实验结果与分析 3.1 实验环境与数据集实验采用4台服务器搭建的Hadoop集群, 主频为双核2.0 GHz, 内存为64 GB, Hadoop的版本为2.8.5, JDK的版本为1.8。
实验采用UCI数据集和TAO数据集, 基准算法为DSTree算法。TAO数据集取自一个热带大气海洋项目, 其中包括12 218个数据流, 每一个数据流的长度为962。本文利用长度为20的移动窗口生成1 268 796个长度为128的子序列。UCI数据集取自UCI资源库, 其中包括18 000条时间序列记录, 本文从中获取670 878个长度为1 000的时间序列集合。
实验还采用了一个模拟数据集, 即所有的时间序列均由随机游走时间序列模型生成, 该数据集包含1 000 000个长度为512的时间序列。
3.2 索引创建时间比较本文对DB-DSTree索引在4个计算节点上的创建时间与DSTree索引在单个计算节点上的创建时间进行比较。分别在TAO数据集和UCI数据集上比较叶子容量为100和300时的情况, 结果如图 4、图 5所示。对于TAO数据集, 由于其大小只有1.1 GB, DSTree索引在内存充裕的情况下采用文件缓存机制, 导致DB-DSTree的创建时间比DSTree的创建时间长。但是对于较大数据集, 如UCI数据集和模拟数据集, DB-DSTree的插入性能优于DSTree。在模拟数据集上, DSTree的创建时间为210 s, DB-DSTree的插入时间为142 s。
|
Download:
|
| 图 4 TAO数据集上索引建立时间的比较 | |
|
Download:
|
| 图 5 UCI数据集上索引建立时间的比较 | |
本文对DB-DSTree索引与DSTree索引的批量查询性能进行比较, 实验结果如图 6~图 8所示。可以看出, DB-DSTree索引的批量查询所用的时间明显比DSTree索引少。在实验中, 路由树DHD的采样β=1, 此时, DB-DSTree的批量查询结果和DSTree的批量查询结果完全一致。由于DB-DSTree具有较好的平衡性和局部性, 在批量查询过程中采用Cache机制, 避免了从HDFS中多次读取DSTree的叶子数据文件, 大幅提高了查询效率。
|
Download:
|
| 图 6 TAO数据集上的批量查询时间比较 | |
|
Download:
|
| 图 7 UCI数据集上的批量查询时间比较 | |
|
Download:
|
| 图 8 模拟数据集上的批量查询时间比较 | |
由上述结果可知, DB-DSTree在索引建立时间和批量查询时间上均优于DSTree。在实验中, DSTree在MapReduce上的实现是随机均分到各个计算节点, 然后各计算节点分别在各子集上建立索引。由于DHD在索引建立和近似查询上都优于DSTree, 且DHD+DSTree的方法建立的分布式索引较为平衡, 因此无论对于256维、512维还是1 024维的数据, 其性能均优于直接进行的DSTree并行化。此外, 维度的改变会导致性能变化, 这是因为维度增加使得距离下界和距离的计算量随之增加。
4 结束语本文提出一种基于MapReduce的分布式时间序列索引DB-DSTree。利用DHD索引对DSTree索引进行并行化处理, 得到双层树结构的DB-DSTree索引。利用批量查询的局部性进行分组, 以有效解决DSTree的非平衡性问题。实验结果表明, 该索引的创建速度较快, 查询效率较高。下一步将基于DB-DSTree对海量时间序列的k-近邻查询进行研究, 并尝试用Spark取代Hadoop, 以充分挖掘分布式内存计算的优势。
| [1] |
WANG Yang, WANG Peng, PEI Jian, et al. A data-adaptive and dynamic segmentation index for whole matching on time series[J]. Proceedings of the VLDB Endowment, 2013, 6(10): 793-804. DOI:10.14778/2536206.2536208 (  0)
|
| [2] |
SHIEH J, KEOGH E.iSAX: indexing and mining terabyte sized time series[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA: ACM Press, 2008: 623-631. https://www.mendeley.com/catalogue/isax-indexing-mining-terabyte-sized-time-series/
( 0)
|
| [3] |
DEAN J, GHEMAWAT S.MapReduce: simplified data processing on large clusters[C]//Proceedings of the 6th Conference on Symposium on Operating Systems Design and Implementation.San Francisco, USA: USENIX Association, 2004: 1-10. http://portal.acm.org/citation.cfm?doid=1327452.1327492
( 0)
|
| [4] |
LI Qiuhong, WANG Peng, WANG Yang, et al.Clustering time series utilizing a dimension hierarchical decomposition approach[C]//Proceedings of International Conference on Database Systems for Advanced Applications.Berlin, Germany: Springer, 2017: 247-261. https://link.springer.com/chapter/10.1007%2F978-3-319-55753-3_16
( 0)
|
| [5] |
CHAN Kinpong, FU A W C.Efficient time series matching by wavelets[C]//Proceedings of the 15th International Conference on Data Engineering.Washington D.C., USA: IEEE Press, 1999: 126-133. https://ieeexplore.ieee.org/document/754915/
( 0)
|
| [6] |
AGRAWAL R, FALOUTSOS C, SWAMI A N.Efficient similarity search in sequence databases[C]//Proceedings of International Conference on Foundations of Data Organization and Algorithms.Berlin, Germany: Springer, 1993: 69-84. https://link.springer.com/chapter/10.1007%2F3-540-57301-1_5
( 0)
|
| [7] |
LIN J, KEOGH E, LONARDI S, et al.A symbolic representation of time series, with implications for streaming algorithms[C]//Proceedings of the 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.New York, USA: ACM Press, 2003: 2-11. https://dl.acm.org/citation.cfm?id=882086
( 0)
|
| [8] |
KORN F, JAGADISH H V, FALOUTSOS C.Efficiently supporting ad hoc queries in large datasets of time sequences[EB/OL].[2019-03-20].http://www.cs.cmu.edu/~christos/PUBLICATIONS.OLDER/sigmod97.pdf.
( 0)
|
| [9] |
KEOGH E, CHAKRABARTI K, PAZZANI M, et al. Locally adaptive dimensionality reduction for indexing large time series databases[J]. ACM Transactions on Database Systems, 2002, 27(2): 188-228. DOI:10.1145/568518.568520 ( 0)
|
| [10] |
KEOGH E, CHAKRABARTI K, PAZZANI M, et al. Dimensionality reduction for fast similarity search in large time series databases[J]. Knowledge and Information Systems, 2001, 3(3): 263-286. DOI:10.1007/PL00011669 ( 0)
|
| [11] |
KEOGH E, CHU S, HART D, et al. Segmenting time series:a survey and novel approach[M]. [S.l.]: World Scientific Publishing Company, 1993.
( 0)
|
| [12] |
陶洋, 李鹏亮, 沈敬红, 等. 基于DTW的时间序列流相似性搜索方法[J]. 计算机工程与设计, 2017, 38(12): 3291-3297. ( 0)
|
| [13] |
ZOUMPATIANOS K, LOU Y, PALPANAS T, et al.Query workloads for data series indexes[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York, USA: ACM Press, 2015: 1603-1612. https://dl.acm.org/citation.cfm?id=2783382
( 0)
|
| [14] |
ZOUMPATIANOS K, PALPANAS T.Data series management: fulfilling the need for big sequence analytics[EB/OL].[2019-03-30]. https://www.irt-systemx.fr/wp-content/uploads/2018/03/Seminar-SystemX_ThemisPalpanas.pdf.
( 0)
|
| [15] |
蔡青林, 陈岭, 梅寒蕾, 等. 基于两级过滤的时间序列近似查询[J]. 浙江大学学报(工学版), 2019, 36(2): 232-236. ( 0)
|
| [16] |
KATE R J. Using dynamic time warping distances as features for improved time series classification[J]. Data Mining and Knowledge Discovery, 2016, 30(2): 283-312. DOI:10.1007/s10618-015-0418-x ( 0)
|
| [17] |
晏臻, 苏维均, 于重重, 等. 一种改进的DTW相似性搜索方法[J]. 计算机仿真, 2016, 50(7): 1290-1297. ( 0)
|
| [18] |
CAMERRA A, PALPANAS T, SHIEH J, et al.iSAX 2.0: indexing and mining one billion time series[C]//Proceedings of 2010 IEEE International Conference on Data Mining.Washington D.C., USA: IEEE Computer Society, 2010: 58-67.
( 0)
|
| [19] |
CAMERRA A, SHIEH J, PALPANAS T, et al. Beyond one billion time series:indexing and mining very large time series collections with iSAX2+[J]. Knowledge and Information Systems, 2014, 39(1): 123-151. DOI:10.1007/s10115-012-0606-6 ( 0)
|
| [20] |
ZOUMPATIANOS K, IDREOS S, PALPANAS T. ADS:the adaptive data series index[J]. The VLDB Journal, 2016, 25(6): 843-866. DOI:10.1007/s00778-016-0442-5 ( 0)
|
| [21] |
KONDYLAKIS H, DAYAN N, ZOUMPATIANOS K, et al.Coconut: a scalable bottom-up approach for building data series indexes[EB/OL].[2019-03-20].https://www.vldb.org/pvldb/vol11/p677-kondylakis.pdf.
( 0)
|