标题：基于集合的时间序列相似性搜索。

编者的总结

1. 本文实际上提出了一种新的时间序列归纳表示法，即基于集合表示序列。其基本思路仍为划分值域空间，取路径中经过的格子作为集合中的元素。以集合交集/Jaccard相似度作为相似性度量。
2. 核心的比较点是这种表示的分类精度，或者说TLB。除此之外，还有归纳表示计算的复杂度，即计算效率。
3. 采用的数据集应该均为内存数据集。

ABSTRACT

本文将时间序列转化成集合，以Jaccard相似性进行度量。
比现有方法要快，某些情况下比DTW要精准。

3. STS3: A SET-BASED TIME SERIES SIMILARITY SEARCH ALGORITHM

3.2 Set Representation for Time Series

首先把序列集占有的空间确定下来（min,max），然后划分格子。每条时间序列途径的格子id，就构成了它的序列表示。

image.png

3.3 The STS3 Algorithm

一个简易的查询算法就是将query也转化成集合表示，然后和数据库里的每个序列算Jaccard相似度，遍历一次选最大的。其计算复杂度是类似于线性扫描。

4. EFFICIENT STS3 ALGORITHMS

作者提了3种方法应对不同长度的序列数据集。

• index-based：长序列
• prunning-based：短序列
• 近似算法：超长序列。

4.1 The Index-based STS3 Algorithm

在每个格子上建立倒排索引，存储包含这个格子的序列，Query经过的格子，一一拿出其中的序列，count++，扫完所有的格子，也就得到一个count列表，对于那些count不等于0的序列，计算Jaccard相似度，找到相似度最高的序列。

image.png

4.2 The Pruning-based STS3 Algorithm

其实就是在cell的上层在做一个zone的概念，一个zone包含几个cell，提前算好数据库里的序列在各个Zone途径cell的数量。query到来时，计算query在各个zone途径cell的数量，那么Query和某序列s的cell交集数的上界就是在各个zone数量较小值的加和。

• 比如有2*2=4个zone，第一个zone里query途径2个cell，s途径1个cell，那么query和s至多相交于1个cell，其他3个zone依次类推，然后做和相加。
• 上界如果比BSF更差的，那就不必再去算真实距离了。
• 每次上界计算的复杂度是O(scale*scale)，即zone的数量；但是算Jaccard的复杂度是O(2n)，n是序列长度，因此可以更加快速进行剪枝。

• scale越大，效率越低，但剪枝率高。

  
  image.png

4.3 The Approximate STS3 Algorithm

• 启发：如果两个序列在细粒度下能碰撞很多格子，那么在粗粒度下应该也不少。而粗粒度的计算和筛选是更快的。
• 算法：
  1. 首先将数据库中的序列从Scale 2=>maxscale 都算一次集合表示存储。（offline，索引构建）
  2. 从小到大遍历每一种Scale，让Query也获得对应scale的集合表示，然后找到最大的zone交集数，交集数不够最大值的序列全部被剪枝。如果交集数为1就break，否则继续下去，直到maxScale。
  3. 剩下的序列，算真实Jaccard相似度。

• 缺陷：这是一种近似算法，因为很有可能会把Jaccard相似度最大的剪枝掉，如下图，原因是启发并不是准确的。

  
  image.png

5. EXTENSIONS

6. DISCUSSIONS OF STS3

7. EXPERIMENTS

【暂时省略】