2019BIGVIS-Progressive Similarity Search on Time Series Data
标题：时间序列similarity-search的一个递进化的方法，使用概率性的质量保证
这两篇论文讲的是同一个问题

编者的总结

1. 本文使用查询时的1NN距离去逐步估计1. 离真实1NN距离还要多久，2.当前result是1NN的概率有多大，3. 真实1NN的距离是多大。
2. 模型分别采用分位数回归，逻辑斯蒂回归，KDE；基本都有对应的道理。

编者的思考

1. 使用的特征还可以再细化一下，只用当前1NN距离可能不够丰富；
2. 使用的模型还可以再优化一下，虽然不能用参数量太大的，但是太简单的线性模型可能对精度有影响。

ABSTRACT

围绕着progressive来说的，指出当前similarity search不能以交互式的响应时间提供，时延较长，本文的progressive逐步提供更精确的结果可以作为一种选择。
其次就是给user提供了一个结果评估的参数，帮助user决定何时终止。

1. INTRODUCTION

主要是围绕着递进式结果来讲的，从一个快速的近似结果，逐步精确，完成交互式的响应。
Contribution主要包括：

• 阐述了在大规模time series data集合中whole-matching 相似性查找的重要性；
• 前置实验证明了，在精确结果1NN出现，和算法终止之间，存在一段无效的时间；
• 发现了高质量的近似结果出现的很早，通常在1s之内，可以满足交互式的响应；
• 基于Adaptive Data Series (ADS)索引，完成KNN-similarity search;
• 开发了一个递进式的similarity search方法

2. STATE OF THE ART

相似性度量：

用的是ED，不过未来会在DTW上继续验证。

similarity search & 交互式查询

各种索引和方法各有所长，本文用的ADS，能够立即获得高质量近似结果，然后快速向精确结果收敛。

Progressive Visual Analytics

本文关注TB级别的数据量，多个data series，每个series都有百到千数量级的维度。
另外一个目标，就是给用户提供近似结果和对这个近似结果不确定度的信息，以帮助用户决定什么时候中止掉搜索。

3. PRELIMINARY OBSERVATIONS

准备实验主要研究递进式的方法是否可能，产生近似结果要多久，近似质量有多好。
实验选了3个100GB的数据集。query就选择了原始数据集中的一段进行similarity search。实验有两个结论：

image.png

第一，第一次获得精确1NN结果的时间是比较短的，但在某些数据集上，也会比较长，但相对于完整搜索的时间来说，都是很短的。这说明精确搜索大部分时间都用于确保搜索结果的精确性，对于结果的质量没有提升。

image.png

第二，第一个近似结果的出现都是非常快的，之后有的快速收敛，有的收敛平缓，无论如何收敛，在1秒之内产出的近似结果，和精确结果距离都非常近。

有了这两个结论，说明递进式的similarity search是可行的，难点在于如何评估近似结果的质量以及是否继续搜索的决策。

基本方法

对于一个数据集，和一个查询序列Q，基于距离分布函数，可以给出一个分布函数，其含义为中至少有一个序列和Q的距离<=x的概率。

image.png
重点问题在于距离分布函数拿不到，只能有一些近似方法：

• Query-Agnostic Approximation
  用来代替，因此与query无关
• Query-Sensitive Approximation
  从queries中随机找一些witnesses，加权平均

两种方法都有局限性。第一，这种静态的1NN距离估计不适用于progressive的方法；第二，好的近似也未必会有好的近似。尤其是在大数据集，n比较大的时候，比较小的近似error都会被n以幂次放大，而尤其会放大在距离最小的那个部分；第三，需要大量的距离计算。因为尤其要捕捉距离最近的sample。

4. PROGRESSIVE SIMILARITY SEARCH

首先是问题的定义：

image.png

虽然没有规定进步的质量，但是确保了质量递增。虽然没有规定精确结果的时长，但是一个good answer通常在交互式的时长内返回结果。
问题主要在于如何衡量中间结果的质量：

• 中间结果和精确结果有多接近？
• 当前结果就是精确结果的概率有多大？
• 预计何时找到精确结果？

5 PREDICTION METHODS

5.1 Initial 1-NN Distance Estimates

本节在Query前就对1NN的距离做出估计
【编者注：不知道这一步有什么意义，可能是用来和baseline对比】

• 一种方法是随机抽出来一部分数据集的点，根据他们的1NN距离分布来确定所有qurey的1NN距离概率分布，这是一个baseline；
• 另一种方法是从Query set里面选出来一部分点当witness，最终当前query的1NN预测距离，由这些witness的1NN距离的加权和来决定

  • 权重是witness和Query的距离来定的，因为越近的点，1NN分布也越接近

    
    image.png

• 这种方法估计出来的只能说线性正相关，要进一步精准预测，作者还用了一个线性回归模型，如下图，用100个query和200个random witness训了一下，结果还可以，在95%的置信区间内基本覆盖了真实值。

  
  image.png

5.2 Progressive 1-NN Distance Estimates

本节在查询过程中，通过逐渐收敛的当前近似1NN距离，预测真实1NN距离。

• 首先iSAX, DSTree索引的首个叶子节点的近似1NN距离和真实1NN距离有很强的相关性。

• 访问更多叶子节点相关性会更强，因此作者基于这个信息去预测真实1NN距离，使得query越到后面，预测真实的概率越大。

  
  image.png

• 接下来就是预测模型了，一种是线性模型，在访问某个给定数量的叶子节点的情况下，通过近似距离去估计精确距离。

  
  image.png
• 另一种就是无参数的（无线性关系假设的），核密度估计（KDE），使用的是高斯核。
• 和线性模型类似，也可以固定一个叶子节点的访问数量，然后去用KDE找关于估计距离和真实距离的一个概率分布；
• 也可以把叶子节点的访问数量也作为一个变量，做一个三元的KDE。

5.3 Estimates for Exact Answers

本节使用近似距离去估计两件事，一个是当前近似距离就是真实距离的概率，另一个是多久（搜多少叶子节点）才能找到真实1NN以及其置信度。

• 作者用了logistic回归来估计第一件事；

  
  image.png

• 结果如下图：每幅图是一个给定访问叶子节点数量时的预测模型，每幅图从右往左看，当前distance越小的越有可能是真实1NN；同样distance，越搜到后面越有可能是真实1NN。

  
  image.png

• 作者用分位数回归来估计第二件事。

• 如下图，搜第一个节点的近似1NN和搜到真实1NN需要的叶子节点数之间的线性关系很弱，但是可以用分位数回归来预测它的上界。比如图中蓝线95%的概率下，搜索至多需要多少叶子节点。

  
  image.png

5.4 Visualization Example

最后我们用一个实例来看看本文的方法怎么用，如下图：

1. 查询开始前就可以有一个1NN距离估计（5.1节witness点+线性回归）
2. 随着查询开始，每个预定义的叶子节点访问数量（图中为1,1024,4096,16384），我们都可以根据此时的近似距离去预测真实距离分布（5.2节KDE）

3. 同时还可以根据该近似距离估计此时已找到1NN的概率（5.3节logistic回归），以及在95%的置信区间下，要找到1NN还需要多少叶子节点。

   
   image.png