以下是论文Exact indexing of dynamic time warping的笔记。

DTW

Dynamic time warping (DTW)是对时间序列更可靠的距离度量方法，允许相似序列匹配，但不适用于精确索引(exact indexing)，在大型数据库中有性能瓶颈。

下界技术

下界技术 (lower bounding measure) 使用快速下界函数修剪不可能成为最佳匹配的序列。伪码：

1
2
3
4
5
6
7
8

best_so_far = infinity;
for all sequences in database
LB_dist = lower_bound_distance(Ci , Q);
    if LB_dist < best_so_far
        true_dist = DTW(Ci , Q);
        if true_dist < best_so_far
            best_so_far = true_dist;
            index_of_best_match = i;

PAA

[1] Piecewise Constant Approximation (PAA)，分段常数近似：将时间序列从n维减少到N维，其中数据库的每一条序列长度都是n，我们想要构建索引的空间维度为N。

[2] 定义MINDIST(Q, R)方法，返回查询Q和最小边界矩形R的距离的下界度量。
假设索引结构包含叶结点U；
最小边界矩形(Minimum Bounding Rectangle)是空间上包含PAA在U中所有的点C的最小的矩形；
R = (L, H)，L为R的主对角线上端点，H为R的主对角线下端点。