以下是论文A Data-adaptive and Dynamic Segmentation Index for Whole Matching on Time Series的笔记。

已有方法及改进

[1] 基于R树的方法、SAX和ISAX：时间序列被划分成等长，所有时间序列以相同方式分段。
[2] 已有的索引结构基于的原则：

• 通过全局切割降维；
• 使用下界技术：确保没有假阴性 (no false negative)结果

D(·, ·)表示距离算法
对于时间序列S，如果DLB(Q, S) > threshold，因为D(Q, S) >= DLB(S1, S2) > threshold，S一定不是相似性查询的结果。

[3] 改进

• 通过局部切割降维可以获得更好的结果从而节约更多的空件和查询响应时间；
• 使用上界技术和下界技术结合

如果DUB(Q, S) < threshold，不必计算D(Q, S)即可得知S是相似性查询的结果。

APCA和EAPCA

[1] APCA (Adaptive Piecewise Constant Approximation)：快速估计两条时间序列之间的距离
[2] EAPCA：扩展APCA，加入标准差，可以获得更紧凑的界限

DSTree

[1] DSTree(dynamic splitting tree)：为时间序列建立数据自适应、动态分割索引。
好处：节约空间和时间，提供时间序列之间距离紧凑的上限和下限。
DSTree的内部节点和叶子结点包含信息如下：

1. 该节点的子树中索引的时间序列数C
2. 该节点索引的时间序列分段SG
3. 用来计算上下界的Z，zi = (μmin, μmax, σmin, σmax)
4. 叶子结点连接到磁盘文件，该文件存储的时间序列最多为ψ，其中ψ是数据树的叶容量；内部节点有两个指向子节点的指针
5. 内部节点存储拆分策略SP

[2] 构建DSTree：对于长度为n的时间序列

1. 初始化：根节点NR，分段SG = (n)，每个时间序列都只包含一个分段
2. 插入：将每个时间序列X分配给叶节点，理想情况下，相似的时间序列分配给相同的叶子结点或子树。
   • 如果根节点NR是叶节点：NR有空间，则访问根节点并将X分配给NR；否则，根据NR的拆分策略SP拆分NR。
   • 如果根节点NR是内部节点：选择NR的更适合X的子节点，然后递归搜索直到找到满足的叶节点。

[3] 将相似的时间序列放入一个叶子结点可以减少在相似性查询过程中I/O操作的次数。

节点拆分策略

[1] 节点拆分策略SP (splitting strategy) = (sid, strategy, measure)

• sid ∈ [1, m] m为分割中选中的片段数
• strategy ∈ {H-split, V-splitL, V-splitR}
• measure ∈ {M, SD}

[2] 节点拆分仅发生于叶子节点没有空间容纳新的时间序列的情况，从而被划分为两个子节点，分配给该节点的时间序列将被分配给拆分过程中创建的两个子节点。

示例

如图：N2的SP = (2, V-splitL, M)，表示第二个片段被选择，使用V-split左边的子片段，H-split的平均数划分；N3的SP = (2, H-split, M)，表示第二个片段被选择，使用H-split的平均数划分。

• H-split：使用平均数或者标准差划分时间序列，分割保持不变
• V-split：首先划分子分割，然后把时间序列按照子分割的平均数聚集

节点拆分策略的质量度量

[1] 时间序列Q的界限范围 (bound range) R(Q) ：时间序列Q和DSTree节点N索引的时间序列之间的距离的上下界限之间的差距，可以用来代表节点N的上下界限的有效性。

[2] Qos：不依赖时间序列，值越小，用于相似性估计的节点的界限的有效性越高。

[3] 拆分利益 (splittiing benefit) B = QosN - (Qosl + Qosr) / 2，B越大，拆分策略越好。其中，QosN表示N的Qos值，Qosl和Qosr分别表示将N拆分成Nl和Nr之后的Qos值。

查询响应算法

相似性搜索

[1] 启发式搜索(heuristic search)只调查一个叶子节点，并找出这个节点中最相似的时间序列。
基于：相似的时间序列常被放在同一个节点中索引（可减少在相似性查询过程中I/O操作的次数）
方法：给定时间序列Q，从根结点开始。如果根节点不是叶子结点，选择NR的更适合Q的子节点，然后递归搜索直到找到满足的叶节点N。计算TSN中每一个时间序列S与Q的距离D(S, Q)，返回距离最短的时间序列。

启发式搜索不能找到整个数据集中最相似的时间序列。

[2] 精确搜索(exact search)：结合启发式搜索和下界距离方法，从而节约空间；

1. 使用启发式搜索返回BSF (best-so-far)结果；
2. 创建优先队列pq用来检验可能包含潜在的比BSF更加相似的时间序列的节点，初始仅包括根节点；
3. 从pq中重复取出具有最小的下界距离的节点，直到pq为空，或者下界距离大于等于BSF的距离。如果下界距离大于等于BSF的距离，那么pq中剩下的时间序列不会成为符合条件的最近邻居，因此可以被剪掉
   • 如果节点是叶子节点，从磁盘中取出时间序列，计算查询时间序列与这些时间序列的距离，记录最小距离。如果最小距离小于BSF，则更新BSF；
   • 如果节点是内部节点，如果子节点与查询时间序列的下界距离小于BSF，则将它的子节点插入pq中。

距离分布直方图

[1] 收集叶子节点的统计信息形成列表L，每一个条目表示落在特定距离范围的时间序列数目。

[2] 因为每两个叶子结点都没有公共元素，所以L中没有冗余的信息，从而获得距离分布直方图Distance Distribution Histogram（假设结点中的时间序列均匀分布）

例如，L = <([10, 20], 10), ([15, 30], 15), ([40, 50], 2)> 表示有3个叶子结点，其中N1包含10条时间序列，与Q的距离在[10, 20]之间。
[15, 20]范围内的时间序列数目为：(15 - 10) / (20 - 10) * 10 + (20 - 15) / (30 - 15) * 15 = 10。

[3] 在某些情况下，子节点的下限/上限可能小于/大于父节点的下限/上限，即父节点中的边界可能比子节点中的边界更紧。在这些子节点上使用边界会导致子节点的估计不准确。
解决方法：如果一个节点中距离的估计范围是[LB, UB]，而它的父节点中距离的估计范围是[LBp, UBp]，那么[max(LB, LBp)，min(UB, UBp)]是该节点的更严格和正确的范围。

[4] α-level使用一些内部节点而不是全部叶子节点更快的建立矩形。
对于每一个从根到叶子节点的路径，选择第⌈α ∗ H⌉个内部节点生成L。
如果路径长度小于⌈α ∗ H⌉，则使用叶节点。