以下是论文KV-Match: A Subsequence Matching Approach Supporting Normalization and Time Warping的笔记。

已有方法及改进

[1] 原有方法：只考虑原始子序列匹配RSM (raw subsequence matching)，不支持子序列归一化(subsequence normalization)；
UCR套件可以处理归一化子序列匹配NSM (normalized subsequence matching)，但是：需要对全时间序列扫描；而且由于完全忽略了偏移位移(offset shifting)和振幅标度(amplitude scaling)，可能会筛选出不符合用户期望的结果。

• RSM：对于时间序列X、查询序列Q（|X| >= |Q|）和距离阈值ε，找到X中所有长度为|Q|的子序列S，满足D(S, Q) <= ε。称为S和Q满足ε-match。
• NSM：对于时间序列X、查询序列Q（|X| >= |Q|）和距离阈值ε，找到X中所有长度为|Q|的子序列S，满足D(SN, QN) <= ε。SN和QN经过归一化（即对每一项s，变为(s - μ) / σ）。

[2] 约束归一化子序列匹配cNSM (constrained normalized subsequence matching)：提供旋钮，可以灵活地控制偏移位移和振幅标度的程度，使用户可以建立索引来处理查询。
偏移位移和振幅标度的范围可以表示某种特定的物理机制或状态，用户通常只希望找到与查询状态相似的子序列。

引入两个限制条件，阈值α (α >= 1) 和 β (β >= 0)：

• cNSM：对于时间序列X、查询序列Q（|X| >= |Q|）和距离阈值ε，找到X中所有长度为|Q|的子序列S，满足D(SN, QN) <= ε，1 / α <= σS / σQ <= α，-β <= μS - μQ <= β。称为S和Q满足(ε, α, β)-match。

α和β分别用来约束偏移位移（与平均数μ有关）和振幅标度（与标准差σ有关）。
α和β值越大，约束条件越松。

[3]KV-index：使用KV-match算法，可以同时支持ED和DTW距离下的支持RSM和cNSM问题（RSM-ED, RSM-DTW, cNSM-ED and cNSM-DTW）。KV-match只需要对索引的一些顺序扫描，而不是像经典R-树索引中随机访问树节点，从而可以提高效率。
KV-matchDP：通过使用不同窗口长度的多个索引，支持任意长度的查询。

KV索引

KV索引结构

[1] KV索引是更紧凑的索引结构，利用数据局部性，即相邻时间点的值接近，因此相邻滑动窗口的平均值也接近。

[2] Ki是滑动窗口平均值的范围 Ki = [lowi, upi)；Vi是落在Ki中的滑动窗口集合，Vi中的位置升序排列，连续的窗口位置会合并到一个窗口区间WI (window interval)。因此Vi中包含一个或多个已排序不相交的窗口区间。

nI(Vi)：Vi中窗口区间的总数，nI(Vi) = {WI |WI ∈ Vi}
nP(Vi)：Vi中窗口位置数。

第一行：三个滑动窗口X(1000, 50), X(1001, 50), X(1002, 50)，平均值落在[1.5, 2.0)；
第二行：三个滑动窗口被划分为两个区间[49, 50], [500, 500]，因此nI(V2) = 2, nP(V2) = 3。
[500, 500]是一个特殊的区间，只包含一个窗口位置。

[4] meta table维护四元组⟨Ki, posi, nI(Vi), nP(Vi)⟩，其中posi是第i行在索引文件中的offset。
meta table很小，可以在执行查询之前加载到内存。
利用meta table，可以利用二分查找快速查到offset和扫描操作的长度。

KV索引建立算法

[1] 首先建立一个索引，所有的行都使用平均值的等宽范围

• 预定义参数d：平均值的范围宽度
• 范围：[k * d, (k + 1) * d)
• 顺序读取X，如果μ(i − 1)在范围Kj中，μi也在范围Kj中 ，则可以把当前的WI右界从i - 1改为i。否则一个新的区间WI = [i, i]会根据μi添加到当前行中。
• 对于曲折的类型如Vi = {[5, 5], [7, 7]}, V(i + 1) = {[6, 6], [8, 8]}，可以合并为Vi = [5, 8]。

[2] 由于数据分布不是每行之间均匀分布，合并相邻的行来优化索引。

• 算法：贪婪算法，归并排序算法
• 预定义参数γ
• 逻辑依据：需要合并的行中有大量的区间是相邻的
• 结果：如果 ⟨Ki, Vi⟩ 和 ⟨Ki+1, Vi+1⟩ 被合并，新的K为 [lowi,up(i+1))，新的V为Vi ∪Vi+1，从Vi到Vi+1的所有相邻窗口区间被合并为一个区间。
• 复杂度：O(nI(Vi) + nI(Vi+1))，所有的窗口区间都会被检查一次

[3] 如果索引大小超过存储能力：

• 第一步把把时间序列划分成为片段，轮流为每一个片段建立固定长度范围的索引。当所有的片段都处理完毕，把不同的片段行合并。
• 第二步顺序访问索引行，也可以划分为子任务。

因为每一步都可以划分为子任务，整个索引建立的算法可以容易地应用到分布式环境，如MapReduce。

[4] 索引建立算法整体复杂度：O(n)

KV-match

• 把给定查询序列Q分割为长度为w的窗口Qi，计算平均值μi。假设|Q|是w的整数倍，否则保留w的最长前缀序列。
• 主过程：
  1. 对于每一个Qi，从KV-index中获取连续行的列表，生成候选子序列SC(subsequence candidates)
  2. 后处理：对CS中的每一个子序列计算实际距离，加以验证
• 四种类型的查询只有主过程的第一步不同，对于每一个窗口，不同的类型有着不同的行范围。

生成窗口区间

• 对于每一个窗口Qi，首先根据查询类型计算μi的范围[LRi, URi]

• 使用单个扫描操作访问KV-index，获得连续行的列表RListi = {⟨Ksi , Vsi⟩ , ⟨Ksi+1, Vsi+1⟩ , … , ⟨Kei , Vei⟩}，满足LRi ∈ [lowsi , upsi) and URi ∈ [lowei , upei)。

  注意：第si行或者第ei行可能包含范围之外的平均值，但是只会带来阴性候选结果，不会漏掉任何阳性候选结果。

• ISi = {WI |WI ∈ Vk,k ∈ [si,ei]}，把区间升序排序，即ISi[k].r < ISi[k + 1].l，其中ISi[k]是ISi中第k个窗口区间。

匹配算法 - 相交(intersection)操作

• 对于窗口Q1，IS1的所有的窗口位置j都map到候选子序列X(j,|Q|)，这样Q1的候选集合CS1就由IS1中的所有位置组成。CS1和IS1一样，由一系列一排序的无相交的窗口区间组成。
• 对于窗口Q2，IS2的所有窗口位置也有相应的CS，但是IS2中的位置j对应的CS中的X(j − w, |Q|)，因为X(j, w)是其第二个窗口。所以Q2点候选集合CS2可以通过把IS2的每一个窗口位置向左移动w获得。
• 类似地，CS3可以通过把IS3的每一个窗口位置向左移动2 * w获得。
  对于窗口Qi，候选集合CSi = {j−(i−1)·w|j ∈ ISi}，所有候选集合都由一系列一排序的无相交的窗口区间组成。
  nI (CSi ) = nI (ISi )， nP (CSi) = nP (ISi)。
  • 如果X(j,|Q|)不包含在CSi中，那么X(j,|Q|)和Q不匹配；
  • 如果X(j,|Q|)和Q匹配，位置j ∈ CSi。

RList1包含WI1、WI2、WI3，RList2包含WI4、WI5、WI6。
IS1包含RList1覆盖的所有区间，IS2包含RList2覆盖的所有区间。
CS1就是IS1，CS2是IS2向左移动w。
将CS1和CS2相交，得到是CS3，包含WI7和WI8。

• 对于CS中每一个WI，取子序列X(WI.l, WI.r − WI.l + |Q|)，这个子序列包含|WI|个子序列。对于每一个长度为|Q|的子序列，计算它与Q的距离，选择合适的子序列返回。
  如果是cNSM查询，每一个子序列都需要在计算ED或者DTW之前归一化。

KV-matchDP

[1] 基本KV-match使用固定窗口长度w处理查询，不考虑查询的长度。
两个限制：

• 支持的查询长度有限
• 很少有机会利用查询和时间序列数据的特性来加快处理速度

[2] KV-matchDP：基于可变窗口长度的多个索引
wu：最小窗口长度，L：索引个数，窗口长度集合：{wu ∗ 2 ^ (i − 1)|1 ≤ i ≤ L}

如果wu = 25，L = 5，建立索引长度分别为：25, 50, 100, 200, 400

动态查询分割

[1] 同时处理多个索引，将Q分割成不同长度的不相交窗口序列{Q1 , Q2 , … , Qp }，用KV-index|Qi|处理每一个Qi。这样可以更加灵活的使用数据特性。

[2] 分割方法：SG = {r1, r2, … , rp}, 意味着Q1 = Q(1, r1), Q2 = Q(r1 + 1, r2 − r1 )…

[3] Q被分割后，剩余步骤和KV-match相同。

质量度量客观方法

[1] 最大影响因素：获取数据

[2] 估计nI(CS)的方法的值的方法：把每一个窗口区间作为X中的一个点，这些位置都是均匀分布的。
CS1中包含区间的概率近似表示为nI(IS1) / n，其中n为X的长度
CS1 ∩ CS2中包含区间的概率表示为nI(IS1) /n * nI(IS2) / n
以此类推，使用几何平均数得到F。F越小，质量越好。

二维动态规划方法

[1] 对于序列Q = (q1, q2, · · · , qm)，
定义搜索空间search space Z = (1,2,··· ,m′)，m′ = ⌊ m / wu ⌋
Z中的值不会影响SG的生成，只会约束SG的搜索空间。
通过寻找Z的SG，然后通过乘wu映射到Q的SG。

如果|Q| = 200, wu = 25, L = 3，即有三个索引KV-index25, KV-index50 和 KV-index100。
SGZ ={2,6,7,8}，SG = {50,150,175,200}，Q 被划分为4个窗口：Q(1,50), Q(51,100), Q(151,25) 和 Q(176, 25)。

[2] 在Z从左到右顺序使用二维动态规划获得优化的SZ。
第一个维度：表示分割的界限
第二个维度：表示一个分割中的窗口数目

[3] 使用vi,j表示计算过程的子状态，与最佳分割Z的前序状态Z(1, i)相关，有j个窗口。
对于任何j(1 <= j <= m’)，最佳分割就是有最小的vm′,j。

φ代表SGZ中在i结束的窗口可能长度，最多有L种可能性。

[4] KV-index中特定行会有很大的nI，导致获取RList有较大的I/O消耗，和每一轮合并CSi的计算消耗。
KV-indexDP可以在某种程度上减轻这种现象，因为客观方法F会选出具有更小的nI的查询窗口。

[5] 更多改进：

• 为了减少访问重复的索引，可以将已经获取的行存在cache中。对每一个RList，如果它的一部分已经在cache中，只需要从KV-index中拿到它的剩下一部分。
• 可以根据RListi的长度重新排序要处理的Qi。RListi的长度可以从meta data中获得。也就是首先处理有较小的RListi的Qi，这样就可以既减小I/O消耗，又减小合并计算消耗。
• 因为每一个CSi都是正确结果的超集，所以可以仅仅处理每一个查询窗口的一部分而不是全部，从而获得最终的CS，且不失去正确率。
  结合第二点和第三点，就可以通过把一些有很大nI的行排序在最下面，从而跳过它们。