2019BIGVIS-Progressive Similarity Search on Time Series Data
標(biāo)題：時間序列similarity-search的一個遞進(jìn)化的方法栋艳，使用概率性的質(zhì)量保證
這兩篇論文講的是同一個問題

編者的總結(jié)

1. 本文使用查詢時的1NN距離去逐步估計(jì)1. 離真實(shí)1NN距離還要多久瞻坝，2.當(dāng)前result是1NN的概率有多大怨愤，3. 真實(shí)1NN的距離是多大。
2. 模型分別采用分位數(shù)回歸癌压，邏輯斯蒂回歸仰泻，KDE；基本都有對應(yīng)的道理滩届。

編者的思考

1. 使用的特征還可以再細(xì)化一下集侯，只用當(dāng)前1NN距離可能不夠豐富；
2. 使用的模型還可以再優(yōu)化一下帜消，雖然不能用參數(shù)量太大的棠枉，但是太簡單的線性模型可能對精度有影響。

ABSTRACT

圍繞著progressive來說的泡挺，指出當(dāng)前similarity search不能以交互式的響應(yīng)時間提供辈讶，時延較長，本文的progressive逐步提供更精確的結(jié)果可以作為一種選擇娄猫。
其次就是給user提供了一個結(jié)果評估的參數(shù)贱除，幫助user決定何時終止咳促。

1. INTRODUCTION

主要是圍繞著遞進(jìn)式結(jié)果來講的，從一個快速的近似結(jié)果勘伺，逐步精確，完成交互式的響應(yīng)褂删。
Contribution主要包括：

• 闡述了在大規(guī)模time series data集合中whole-matching 相似性查找的重要性飞醉；
• 前置實(shí)驗(yàn)證明了，在精確結(jié)果1NN出現(xiàn)屯阀，和算法終止之間缅帘，存在一段無效的時間；
• 發(fā)現(xiàn)了高質(zhì)量的近似結(jié)果出現(xiàn)的很早难衰，通常在1s之內(nèi)钦无，可以滿足交互式的響應(yīng)；
• 基于Adaptive Data Series (ADS)索引盖袭，完成KNN-similarity search;
• 開發(fā)了一個遞進(jìn)式的similarity search方法

2. STATE OF THE ART

相似性度量：

用的是ED失暂，不過未來會在DTW上繼續(xù)驗(yàn)證。

similarity search & 交互式查詢

各種索引和方法各有所長鳄虱，本文用的ADS弟塞，能夠立即獲得高質(zhì)量近似結(jié)果，然后快速向精確結(jié)果收斂拙已。

Progressive Visual Analytics

本文關(guān)注TB級別的數(shù)據(jù)量决记，多個data series，每個series都有百到千數(shù)量級的維度倍踪。
另外一個目標(biāo)系宫，就是給用戶提供近似結(jié)果和對這個近似結(jié)果不確定度的信息，以幫助用戶決定什么時候中止掉搜索建车。

3. PRELIMINARY OBSERVATIONS

準(zhǔn)備實(shí)驗(yàn)主要研究遞進(jìn)式的方法是否可能扩借，產(chǎn)生近似結(jié)果要多久，近似質(zhì)量有多好癞志。
實(shí)驗(yàn)選了3個100GB的數(shù)據(jù)集往枷。query就選擇了原始數(shù)據(jù)集中的一段進(jìn)行similarity search。實(shí)驗(yàn)有兩個結(jié)論：

image.png

第一凄杯，第一次獲得精確1NN結(jié)果的時間是比較短的错洁，但在某些數(shù)據(jù)集上，也會比較長戒突，但相對于完整搜索的時間來說屯碴，都是很短的。這說明精確搜索大部分時間都用于確保搜索結(jié)果的精確性膊存，對于結(jié)果的質(zhì)量沒有提升导而。

image.png

第二忱叭，第一個近似結(jié)果的出現(xiàn)都是非常快的今艺，之后有的快速收斂韵丑，有的收斂平緩，無論如何收斂虚缎，在1秒之內(nèi)產(chǎn)出的近似結(jié)果撵彻，和精確結(jié)果距離都非常近。

有了這兩個結(jié)論实牡，說明遞進(jìn)式的similarity search是可行的陌僵，難點(diǎn)在于如何評估近似結(jié)果的質(zhì)量以及是否繼續(xù)搜索的決策。

基本方法

對于一個數(shù)據(jù)集创坞，和一個查詢序列Q碗短，基于距離分布函數(shù)，可以給出一個分布函數(shù)题涨，其含義為中至少有一個序列和Q的距離<=x的概率偎谁。

image.png

• Query-Agnostic Approximation
  用來代替纲堵，因此與query無關(guān)
• Query-Sensitive Approximation
  從queries中隨機(jī)找一些witnesses搭盾，加權(quán)平均

兩種方法都有局限性。第一婉支，這種靜態(tài)的1NN距離估計(jì)不適用于progressive的方法鸯隅；第二，好的近似也未必會有好的近似向挖。尤其是在大數(shù)據(jù)集蝌以，n比較大的時候，比較小的近似error都會被n以冪次放大何之，而尤其會放大在距離最小的那個部分跟畅；第三，需要大量的距離計(jì)算溶推。因?yàn)橛绕湟蹲骄嚯x最近的sample徊件。

4. PROGRESSIVE SIMILARITY SEARCH

首先是問題的定義：

image.png

雖然沒有規(guī)定進(jìn)步的質(zhì)量，但是確保了質(zhì)量遞增蒜危。雖然沒有規(guī)定精確結(jié)果的時長虱痕，但是一個good answer通常在交互式的時長內(nèi)返回結(jié)果。
問題主要在于如何衡量中間結(jié)果的質(zhì)量：

• 中間結(jié)果和精確結(jié)果有多接近辐赞？
• 當(dāng)前結(jié)果就是精確結(jié)果的概率有多大部翘？
• 預(yù)計(jì)何時找到精確結(jié)果？

5 PREDICTION METHODS

5.1 Initial 1-NN Distance Estimates

本節(jié)在Query前就對1NN的距離做出估計(jì)
【編者注：不知道這一步有什么意義响委，可能是用來和baseline對比】

• 一種方法是隨機(jī)抽出來一部分?jǐn)?shù)據(jù)集的點(diǎn)新思，根據(jù)他們的1NN距離分布來確定所有qurey的1NN距離概率分布窖梁，這是一個baseline；
• 另一種方法是從Query set里面選出來一部分點(diǎn)當(dāng)witness夹囚，最終當(dāng)前query的1NN預(yù)測距離纵刘，由這些witness的1NN距離的加權(quán)和來決定

  • 權(quán)重是witness和Query的距離來定的，因?yàn)樵浇狞c(diǎn)荸哟，1NN分布也越接近

    
    
    image.png

• 這種方法估計(jì)出來的只能說線性正相關(guān)彰导，要進(jìn)一步精準(zhǔn)預(yù)測，作者還用了一個線性回歸模型敲茄，如下圖，用100個query和200個random witness訓(xùn)了一下山析，結(jié)果還可以堰燎，在95%的置信區(qū)間內(nèi)基本覆蓋了真實(shí)值。

  
  
  image.png

5.2 Progressive 1-NN Distance Estimates

本節(jié)在查詢過程中笋轨，通過逐漸收斂的當(dāng)前近似1NN距離秆剪，預(yù)測真實(shí)1NN距離。

• 首先iSAX, DSTree索引的首個葉子節(jié)點(diǎn)的近似1NN距離和真實(shí)1NN距離有很強(qiáng)的相關(guān)性爵政。

• 訪問更多葉子節(jié)點(diǎn)相關(guān)性會更強(qiáng)仅讽，因此作者基于這個信息去預(yù)測真實(shí)1NN距離，使得query越到后面钾挟，預(yù)測真實(shí)的概率越大洁灵。

  
  
  image.png

• 接下來就是預(yù)測模型了，一種是線性模型掺出，在訪問某個給定數(shù)量的葉子節(jié)點(diǎn)的情況下徽千，通過近似距離去估計(jì)精確距離。

  
  
  image.png
• 另一種就是無參數(shù)的（無線性關(guān)系假設(shè)的）汤锨，核密度估計(jì)（KDE）双抽，使用的是高斯核。
• 和線性模型類似闲礼，也可以固定一個葉子節(jié)點(diǎn)的訪問數(shù)量牍汹，然后去用KDE找關(guān)于估計(jì)距離和真實(shí)距離的一個概率分布；
• 也可以把葉子節(jié)點(diǎn)的訪問數(shù)量也作為一個變量柬泽，做一個三元的KDE慎菲。

5.3 Estimates for Exact Answers

本節(jié)使用近似距離去估計(jì)兩件事，一個是當(dāng)前近似距離就是真實(shí)距離的概率锨并，另一個是多久（搜多少葉子節(jié)點(diǎn)）才能找到真實(shí)1NN以及其置信度钧嘶。

• 作者用了logistic回歸來估計(jì)第一件事；

  
  
  image.png

• 結(jié)果如下圖：每幅圖是一個給定訪問葉子節(jié)點(diǎn)數(shù)量時的預(yù)測模型琳疏，每幅圖從右往左看有决，當(dāng)前distance越小的越有可能是真實(shí)1NN闸拿；同樣distance，越搜到后面越有可能是真實(shí)1NN书幕。

  
  
  image.png

• 作者用分位數(shù)回歸來估計(jì)第二件事新荤。

• 如下圖，搜第一個節(jié)點(diǎn)的近似1NN和搜到真實(shí)1NN需要的葉子節(jié)點(diǎn)數(shù)之間的線性關(guān)系很弱台汇，但是可以用分位數(shù)回歸來預(yù)測它的上界苛骨。比如圖中藍(lán)線95%的概率下，搜索至多需要多少葉子節(jié)點(diǎn)苟呐。

  
  
  image.png

5.4 Visualization Example

最后我們用一個實(shí)例來看看本文的方法怎么用痒芝，如下圖：

1. 查詢開始前就可以有一個1NN距離估計(jì)（5.1節(jié)witness點(diǎn)+線性回歸）
2. 隨著查詢開始，每個預(yù)定義的葉子節(jié)點(diǎn)訪問數(shù)量（圖中為1,1024,4096,16384）牵素，我們都可以根據(jù)此時的近似距離去預(yù)測真實(shí)距離分布（5.2節(jié)KDE）

3. 同時還可以根據(jù)該近似距離估計(jì)此時已找到1NN的概率（5.3節(jié)logistic回歸）严衬，以及在95%的置信區(qū)間下，要找到1NN還需要多少葉子節(jié)點(diǎn)笆呆。

   
   
   image.png