标题：时序数据中的twin子序列搜索

编者的思考：

1. 本文基于切比雪夫距离做similarity search，距离衡量是比较新颖的，但是索引/查询方法不算新颖，基本上基于iSAX的思路，首先对序列进行表示，然后按范围层次化构建索引，用插入的方法找近似和距离下界，再提供剪枝方法。本文甚至都没用表示法，只用了全序列切比雪夫距离的计算找最接近的节点，算法还有很多改进的空间。
2. 本文做的是subsequence matching，但是没有挖掘到overlapping, continuous的关系(ULISSE)，粗粒度的把所有subsequence加入索引中，还有优化空间。

ABSTRACT

本文是基于切比雪夫距离的subsequence matching，称为twin subsequence。
首先改造了现有的索引方法，使之可以计算此问题；然后定制设计了TS-Tree Index，效果更好。

1. INTRODUCTION

用了一幅图来表达某些时候切比雪夫距离比ED更容易捕捉序列特征。

image.png

实现twin search，可以用sweepline顺序横扫，但太慢，UCR Suite的方法不适用于此。
改造的索引方法有KV-Index和iSAX，设计了一个filter-verification进行改造。定制的索引用了Minimun Bounding Time Series（MBTS），在每个节点都有一个upper/lower bound series。

2. RELATED WORK

• sweepline的UCR Suite和Matrix Profile，不适用于切比雪夫距离；
• wavelet信号比较古老的降维，后来有SAX分支的多种方法，ADS+基于query workload有自适应，MESSI,ParIs做了分布式；
• 最近有KV-index；
• 通用的任意 norm index方法；
• 之前做了基于切比雪夫距离的pair和bundle的挖掘，用的是sweepline的方法；后来又对地理数据，基于ED和MBTS做了索引。

3. PROBLEM DEFINITION

3.1 Problem Statement

twin subsequence和ED之间有一定关系，如下图：

image.png

有关z-normalization方面，作者提供了三种方案，RSM，NSM，先全序列norm了之后，再SM。

3.2 Filter-verification approach

思路是先筛出candidate，然后再计算精确距离进行verification，如果是z-norm的，可以先选Q中绝对值大的点，可以做early abondon，类似于UCR Suite的技术。

4. TWIN SUBSEQUENCE SEARCH WITH EXISTING INDICES

主要思想是如果两个序列是twins，即它们对应位置的极值差都不超过，那么它们的均值差也不超过。
还有，如果两个序列是twins，那么它们中的任一对对应的子序列，也是twins。

4.1 KV-Index

因为均值有范围了，所以KV-index也可以用了，但是不适用于NSM。

4.2 iSAX

每一个segment均值皆有范围，iSAX树索引可以做LB近似判断，也可以使用。

5. THE TS-INDEX

上面两个算法，用于此场景时，会有大量的假阳性，性能不高，下面提出定制款。

5.1 Index Structure

MBTS，是一组时间序列的包络序列，每个位置都取相应位置的极值，进行包络。
索引也是类似的结构，每个叶子节点指向一组subsequences，用MBTS进行summarize。中间节点指向若干叶子，也是这些叶子的MBTS，越向根部越松，范围越宽。所有叶子节点永远在同一个level上。

5.2 Index Construction

中间节点有下层孩子节点，叶子节点的孩子节点就是各个subsequences，扇出有区间限制。
插入的时候逐层选择距离最小的节点进行继续。
一旦插入溢出（叶子节点就是承载足够多的序列，中间节点就是超出扇出限制），就要分裂成两个同层兄弟节点。对于叶子节点，分裂就选两个种子subsequence（距离最远的），然后对剩下的subsequences依次进行选择插入，目标函数是MBTS的扩张要尽可能小。对于内部节点，就要选择两个基线子节点，然后计算其他子节点和基线子节点的距离，选距离小的插入。
注意，这样的分裂方式，是会向上传播的，即下层节点的分裂可能会导致上层节点的扇出增加，然后也要分裂，逐级向上传递。
也就是说，这是一颗向上生长的树（类似B+树）。

5.3 Query Execution

查询基于的一个Lemma是：如果Q和某个subsequence S是twins，那么它和包络S的区域B的距离一定不大于
接下来就是遍历+剪枝了。对于z-norm，也可以实现early abondon。

image.png

6. EXPERIMENTAL EVALUATION

image.png

在Query Length，数据集都很小的情况下做的实验，比对应的iSAX和KV-INDEX略好，仍需敲定。