2020SIGMOD-Data Series Progressi

2023-09-06  本文已影响0人  Caucher

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主要包括:

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是可行的,难点在于如何评估近似结果的质量以及是否继续搜索的决策。

基本方法

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

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

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

4. PROGRESSIVE SIMILARITY SEARCH

首先是问题的定义:


image.png

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

5 PREDICTION METHODS

5.1 Initial 1-NN Distance Estimates

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

5.2 Progressive 1-NN Distance Estimates

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

5.3 Estimates for Exact Answers

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

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
上一篇 下一篇

猜你喜欢

热点阅读