2019BIGVIS-Progressive Similarity Search on Time Series Data
標題：時間序列similarity-search的一個遞進化的方法，使用概率性的質(zhì)量保證
這兩篇論文講的是同一個問題
編者的總結(jié)
- 本文使用查詢時的1NN距離去逐步估計1. 離真實1NN距離還要多久，2.當前result是1NN的概率有多大，3. 真實1NN的距離是多大。
- 模型分別采用分位數(shù)回歸，邏輯斯蒂回歸，KDE；基本都有對應(yīng)的道理。
編者的思考
- 使用的特征還可以再細化一下，只用當前1NN距離可能不夠豐富；
- 使用的模型還可以再優(yōu)化一下，雖然不能用參數(shù)量太大的，但是太簡單的線性模型可能對精度有影響。
ABSTRACT
圍繞著progressive來說的，指出當前similarity search不能以交互式的響應(yīng)時間提供，時延較長，本文的progressive逐步提供更精確的結(jié)果可以作為一種選擇。
其次就是給user提供了一個結(jié)果評估的參數(shù)，幫助user決定何時終止。
1. INTRODUCTION
主要是圍繞著遞進式結(jié)果來講的，從一個快速的近似結(jié)果，逐步精確，完成交互式的響應(yīng)。
Contribution主要包括：
- 闡述了在大規(guī)模time series data集合中whole-matching 相似性查找的重要性；
- 前置實驗證明了，在精確結(jié)果1NN出現(xiàn)，和算法終止之間，存在一段無效的時間；
- 發(fā)現(xiàn)了高質(zhì)量的近似結(jié)果出現(xiàn)的很早，通常在1s之內(nèi)，可以滿足交互式的響應(yīng)；
- 基于Adaptive Data Series (ADS)索引，完成KNN-similarity search;
- 開發(fā)了一個遞進式的similarity search方法
2. STATE OF THE ART
相似性度量：
用的是ED，不過未來會在DTW上繼續(xù)驗證。
similarity search & 交互式查詢
各種索引和方法各有所長，本文用的ADS，能夠立即獲得高質(zhì)量近似結(jié)果，然后快速向精確結(jié)果收斂。
Progressive Visual Analytics
本文關(guān)注TB級別的數(shù)據(jù)量，多個data series，每個series都有百到千數(shù)量級的維度。
另外一個目標，就是給用戶提供近似結(jié)果和對這個近似結(jié)果不確定度的信息，以幫助用戶決定什么時候中止掉搜索。
3. PRELIMINARY OBSERVATIONS
準備實驗主要研究遞進式的方法是否可能，產(chǎn)生近似結(jié)果要多久，近似質(zhì)量有多好。
實驗選了3個100GB的數(shù)據(jù)集。query就選擇了原始數(shù)據(jù)集中的一段進行similarity search。實驗有兩個結(jié)論：
第一，第一次獲得精確1NN結(jié)果的時間是比較短的，但在某些數(shù)據(jù)集上，也會比較長，但相對于完整搜索的時間來說，都是很短的。這說明精確搜索大部分時間都用于確保搜索結(jié)果的精確性，對于結(jié)果的質(zhì)量沒有提升。
第二，第一個近似結(jié)果的出現(xiàn)都是非?？斓?，之后有的快速收斂，有的收斂平緩，無論如何收斂，在1秒之內(nèi)產(chǎn)出的近似結(jié)果，和精確結(jié)果距離都非常近。
有了這兩個結(jié)論，說明遞進式的similarity search是可行的，難點在于如何評估近似結(jié)果的質(zhì)量以及是否繼續(xù)搜索的決策。
基本方法
對于一個數(shù)據(jù)集，和一個查詢序列Q，基于距離分布函數(shù)，可以給出一個分布函數(shù)，其含義為
中至少有一個序列和Q的距離<=x的概率。
重點問題在于距離分布函數(shù)
- Query-Agnostic Approximation
用來代替
，因此與query無關(guān)
- Query-Sensitive Approximation
從queries中隨機找一些witnesses，加權(quán)平均
兩種方法都有局限性。第一，這種靜態(tài)的1NN距離估計不適用于progressive的方法；第二，好的近似也未必會有好的
近似。尤其是在大數(shù)據(jù)集，n比較大的時候，比較小的近似error都會被n以冪次放大，而
尤其會放大
在距離最小的那個部分；第三，需要大量的距離計算。因為尤其要捕捉距離最近的sample。
4. PROGRESSIVE SIMILARITY SEARCH
首先是問題的定義：
雖然沒有規(guī)定進步的質(zhì)量，但是確保了質(zhì)量遞增。雖然沒有規(guī)定精確結(jié)果的時長，但是一個good answer通常在交互式的時長內(nèi)返回結(jié)果。
問題主要在于如何衡量中間結(jié)果的質(zhì)量：
- 中間結(jié)果和精確結(jié)果有多接近？
- 當前結(jié)果就是精確結(jié)果的概率有多大？
- 預(yù)計何時找到精確結(jié)果？
5 PREDICTION METHODS
5.1 Initial 1-NN Distance Estimates
本節(jié)在Query前就對1NN的距離做出估計
【編者注：不知道這一步有什么意義，可能是用來和baseline對比】
- 一種方法是隨機抽出來一部分數(shù)據(jù)集的點，根據(jù)他們的1NN距離分布來確定所有qurey的1NN距離概率分布，這是一個baseline；
- 另一種方法是從Query set里面選出來一部分點當witness，最終當前query的1NN預(yù)測距離，由這些witness的1NN距離的加權(quán)和來決定
-
權(quán)重是witness和Query的距離來定的，因為越近的點，1NN分布也越接近
image.png
-
-
這種方法估計出來的只能說線性正相關(guān)，要進一步精準預(yù)測，作者還用了一個線性回歸模型，如下圖，用100個query和200個random witness訓(xùn)了一下，結(jié)果還可以，在95%的置信區(qū)間內(nèi)基本覆蓋了真實值。
image.png
5.2 Progressive 1-NN Distance Estimates
本節(jié)在查詢過程中，通過逐漸收斂的當前近似1NN距離，預(yù)測真實1NN距離。
- 首先iSAX, DSTree索引的首個葉子節(jié)點的近似1NN距離和真實1NN距離有很強的相關(guān)性。
-
訪問更多葉子節(jié)點相關(guān)性會更強，因此作者基于這個信息去預(yù)測真實1NN距離，使得query越到后面，預(yù)測真實的概率越大。
image.png -
接下來就是預(yù)測模型了，一種是線性模型，在訪問某個給定數(shù)量的葉子節(jié)點的情況下，通過近似距離去估計精確距離。
image.png - 另一種就是無參數(shù)的（無線性關(guān)系假設(shè)的），核密度估計（KDE），使用的是高斯核。
- 和線性模型類似，也可以固定一個葉子節(jié)點的訪問數(shù)量，然后去用KDE找關(guān)于估計距離和真實距離的一個概率分布；
- 也可以把葉子節(jié)點的訪問數(shù)量也作為一個變量，做一個三元的KDE。
5.3 Estimates for Exact Answers
本節(jié)使用近似距離去估計兩件事，一個是當前近似距離就是真實距離的概率，另一個是多久（搜多少葉子節(jié)點）才能找到真實1NN以及其置信度。
-
作者用了logistic回歸來估計第一件事；
image.png -
結(jié)果如下圖：每幅圖是一個給定訪問葉子節(jié)點數(shù)量時的預(yù)測模型，每幅圖從右往左看，當前distance越小的越有可能是真實1NN；同樣distance，越搜到后面越有可能是真實1NN。
image.png 作者用分位數(shù)回歸來估計第二件事。
-
如下圖，搜第一個節(jié)點的近似1NN和搜到真實1NN需要的葉子節(jié)點數(shù)之間的線性關(guān)系很弱，但是可以用分位數(shù)回歸來預(yù)測它的上界。比如圖中藍線95%的概率下，搜索至多需要多少葉子節(jié)點。
image.png
5.4 Visualization Example
最后我們用一個實例來看看本文的方法怎么用，如下圖：
- 查詢開始前就可以有一個1NN距離估計（5.1節(jié)witness點+線性回歸）
- 隨著查詢開始，每個預(yù)定義的葉子節(jié)點訪問數(shù)量（圖中為1,1024,4096,16384），我們都可以根據(jù)此時的近似距離去預(yù)測真實距離分布（5.2節(jié)KDE）
-
同時還可以根據(jù)該近似距離估計此時已找到1NN的概率（5.3節(jié)logistic回歸），以及在95%的置信區(qū)間下，要找到1NN還需要多少葉子節(jié)點。
image.png
