2018PVLDB-Scalable, Variable-Length Similarity Search in Data Series:
The ULISSE Approach
這兩篇文章是同作者產(chǎn)出的，一個(gè)是會(huì)議，一個(gè)是期刊，前者只有4頁，講的實(shí)在是過于模糊了，建議看后者期刊的論文，講的比較清楚（仍有一些小筆誤）。

編者的總結(jié)

這篇論文的核心是將一組overlapping, continuous的，或者是僅在長度上有區(qū)別的subsequences進(jìn)行歸納，基于iSAX提出了個(gè)uENV的表示法，用于表示其上下界限，進(jìn)而提出了下界距離定義公式，以支持KNN-similarty search。
一個(gè)比較重要的參數(shù) $\gamma$ 表示一個(gè)uENV的接管范圍，能讓這個(gè)方法更為靈活。
基于uENV的表示，能夠造出類似iSAX的索引，使得一定長度范圍內(nèi)的query series，都可以和一組data series C進(jìn)行KNN-similarty search，其結(jié)果將在C的所有等長子序列中進(jìn)行選擇。
這個(gè)可變長度的搜索較好地?cái)U(kuò)展了iSAX-similarty search的實(shí)用性，雖然在性能上有所犧牲，但這也主要源于搜索空間上變大了幾個(gè)數(shù)量級。

編者的思考

這篇論文是基于iSAX做的一個(gè)可變長度的擴(kuò)展，所以iSAX的問題，這里也都存在，這個(gè)作者在Conclusion也提到，future work會(huì)研究少量長序列的索引。
uENV這種表示方法感覺信息缺失比較多，其只保留了PAA極值，但對于KNN-similarty search來說確實(shí)足夠了。但是如果能更好(信息更豐富)的歸納這樣一組subsequences，也許會(huì)對其它類型的索引、算法也有更好的幫助。

標(biāo)題：時(shí)序數(shù)據(jù)中，對于可變長度的相似性搜索，構(gòu)造了高壓縮的索引

Abstract

目前的時(shí)序數(shù)據(jù)索引可以進(jìn)行相似性查找，但是長度是固定的，在索引創(chuàng)建時(shí)固定下來。本文設(shè)計(jì)的ULISSE可以實(shí)現(xiàn)可變長度的查找。
本文的貢獻(xiàn)是兩方面：

設(shè)計(jì)了一種representation，可以高效歸納多個(gè)不等長序列
基于ULISSE索引，設(shè)計(jì)了結(jié)合磁盤索引查找和內(nèi)存順序搜索的相似性查找算法。

1. Introduction

問題主要是針對變長相似性搜索來說的，已有的文獻(xiàn)里有定長的搜索，通過對定長搜索的簡單重復(fù)，可以搞出變長相似性搜索，但是時(shí)間空間都是爆炸增長。也有文獻(xiàn)對這種重復(fù)進(jìn)行優(yōu)化，但是只是緩解了問題，沒有徹底解決爆炸增長的問題，還沒有進(jìn)行Z-normalize。
本文提出的是第一個(gè)single index。就是不再對可能查詢的每一個(gè)長度建index再考慮優(yōu)化，而是只建立一個(gè)。基于的思想就是一個(gè)序列的索引里包含的信息肯定包含它的子序列索引里的信息。那么問題就在于如何重新組織索引里的信息，ULISSE的主要貢獻(xiàn)，就是做了這樣的一個(gè)summerization. 是否進(jìn)行Z-normalization都可以算。

2. Related Work

定長索引
基于定長的思路，做的不定長索引，還是前面的兩個(gè)問題
單個(gè)長序列中多個(gè)子序列之間的matching場景中，序列化的scan非常高效（本文的場景時(shí)大量短序列，以此說明仍需索引）

3. Preliminaries

subsequence子序列定義為連續(xù)的
Z-normalize
歐氏距離
Piecewise Aggregate Approximation（PAA），分段聚合，將序列D，每長度s分割成一個(gè)segment，取個(gè)均值，構(gòu)成一個(gè)長度為w的向量，即將D在w維空間中進(jìn)行表示，記做PAA(D)
iSAX
問題:VARIABLE-LENGTH SUBSEQUENCES INDEXING：給定一個(gè)data series集合C，和一個(gè)長度范圍，建立一個(gè)索引要能支持在這個(gè)長度范圍內(nèi)的任意query series進(jìn)行similarty search
similarty search：作者在這里將其定義為KNN問題，對于一個(gè)data series集合C，一個(gè)query series Q，其長度在一定范圍內(nèi)，任意C中長度等于Q的子序列都可以成為備選，選出其中距離最小的K個(gè)，就是KNN問題。

4. Proposed Approach

在說明方法之前，還是重申一下，這個(gè)論文方法的目的是為了能夠高效歸納出一組連續(xù)的，overlapping的子序列，而不是對每個(gè)長度范圍內(nèi)的子序列都視為一個(gè)獨(dú)立的序列。接下來以一個(gè)Data Series D為例，說明如何做這種summerization.

A. Representing Multiple Subsequences

首先給出一個(gè)master series的定義，對于D，和一個(gè)長度范圍 $[l_{min},l_{max}]$ ，master series是D的一個(gè)subsequence，長度盡可能為 $l_{max}$ ，如果到了序列終點(diǎn)了，長度可以不足 $l_{max}$ ，但是最短不能短于 $l_{min}$ 。
如果只關(guān)心前k個(gè)PAA值，那么master series足以代表相同起點(diǎn)的所有長度范圍內(nèi)的subsequence。所以之后我們只研究master series。
假設(shè)D的起始位點(diǎn)為 $\alpha$ ，我們首先找出起始位點(diǎn)在 $[\alpha,\alpha+\gamma]$ 范圍內(nèi)的所有master series（一共 $\gamma+1$ 個(gè)）；將這些master series進(jìn)行zero align平移，如下圖，然后取PAA，通過在每個(gè)segment范圍內(nèi)找極值，我們在每個(gè)segment范圍內(nèi)，構(gòu)成了一個(gè)containment area和一對envelope extremes。

image.png

B. PAA Envelope

這里對PAA envelope給了一個(gè)形式化定義，如下圖：

image.png

這個(gè)L,U其實(shí)是一個(gè)向量，表示每個(gè)segment對應(yīng)的PAA 最大值和最小值。

C. PAA Envelope for Z-Normalized subsequence

先略過，之后更新

4. Indexing the Envelopes

$uENV_{paaENV_{[D,l_{min},l_{max},\alpha,\gamma,s]}} =[iSAX(L), iSAX(U)]$
首先是這樣一個(gè)uENV的定義，對剛才的paaENV取個(gè)iSAX，就是uENV了。后面我們會(huì)講到，通過uENV，query和一個(gè)uENV里的所有子序列（長度范圍在 $[l_{min},l_{max}]之間$ ）的距離可以估算出一個(gè)下界距離來。

5. INDEXING ALGORITHM

5.1 Non Z-Normalized Subsequences

這里作者提供了一個(gè)算法，用了一個(gè)滑動(dòng)窗口的算法，還比較巧妙，可以完成uENV的計(jì)算。時(shí)間復(fù)雜度為 $O(w(l_{max} + \gamma))$ 。
注意到其中 $l_{max} + \gamma$ 是為了能計(jì)算第 $\gamma$ 個(gè)子序列的最后一段PAA值。另外， $\gamma$ 這個(gè)參數(shù)也比較有趣，它其實(shí)決定了這樣計(jì)算出來的uENV最遠(yuǎn)能覆蓋到多大的x坐標(biāo)，這樣意味著，如果 $\gamma<l_{max}$ 上圖的containment area會(huì)在x軸方向重疊。

5.2 Z-Normalized Subsequences

先略過，之后更新。

5.3 Building the index

首先上一個(gè)索引的構(gòu)建圖。

image.png

索引是一個(gè)樹形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)都包含一個(gè)iSAX(L)和一個(gè)iSAX(U)，就是一個(gè)抽象的uENV，代表這個(gè)節(jié)點(diǎn)在各個(gè)segment的上下界。其中葉子節(jié)點(diǎn)包括一系列具體的uENV，每個(gè)uENV能夠指向一組subsequence(起始位點(diǎn)連續(xù)在 $\gamma$ 范圍內(nèi)，長度在 $[l_{min},l_{max}]$ 范圍內(nèi)，這一組subsequence只需要指定 $\alpha$ 和序列id即可確定)。
索引可以按照iSAX(L)進(jìn)行組織，也可以按照iSAX(U)進(jìn)行組織，這里選擇的是iSAX(L)。每個(gè)葉子節(jié)點(diǎn)都有一組相同的iSAX(L)的具體uENV。

現(xiàn)在的一個(gè)問題就是給定一個(gè)data series collection C，什么樣的uENV可以插入到索引里？對于C中的每一個(gè)data series D， $\alpha$ 從0開始，以 $\gamma+1$ 為步長，分別構(gòu)建uENV，插入到索引中。正如我們剛才所說， $\gamma$ 決定了一個(gè)uENV能輻射多長的x軸。

最后插入uENV到葉子節(jié)點(diǎn)之后，要更新這條更新路徑上所有節(jié)點(diǎn)的iSAX(U)。
除了索引以外，算法還將所有的uENV以最高位的基數(shù)存在內(nèi)存中。

5.3.1 Space complexity analysis

索引的空間復(fù)雜度占用為 $O((2w)bN)$ ，N是uENV個(gè)數(shù)，即需要索引的subsequence個(gè)數(shù)，極大程度取決于 $\gamma$

6. SIMILARITY SEARCH WITH ULISSE

6.1 Lower Bounding Euclidean Distance

iSAX支持定義MINDIST距離公式，使得MINDIST是ED的一個(gè)下界。作者給了一個(gè)MINDIST的定義公式，這個(gè)距離代表一個(gè)query series Q，和一組subsequence的距離。

image.png

作者隨后即證明了對于任意的

\alpha=<i<=\alpha + \gamma + 1

，

D_{i,|Q|}

和Q之間的ED距離都比MINDIST要大。

編者注：其實(shí)也可以推論，如果這個(gè)uENV越松，就是范圍越大，那么MINDIST這個(gè)下界也會(huì)越松。

6.2 Approximate search

近似搜索算法還是遵循了iSAX的思想，采用一個(gè)優(yōu)先級隊(duì)列，按照和Q的MINDIST進(jìn)行排序，internal node直接入隊(duì)兩個(gè)孩子，葉子節(jié)點(diǎn)則要對涵蓋的每一個(gè)真實(shí)uENV(subsequence)進(jìn)行讀取，然后計(jì)算ED，更新KNN。注意這一步，一個(gè)uENV會(huì)涵蓋至少 $\gamma$ 個(gè)備選子序列，也會(huì)計(jì)算 $\gamma$ 次ED。
從上面的來看，其實(shí)算的是精確結(jié)果，為什么說是近似呢，源于它的終止條件。這個(gè)算法并不會(huì)遍歷所有的葉子節(jié)點(diǎn)，當(dāng)從隊(duì)列中出隊(duì)一個(gè)葉子節(jié)點(diǎn)，經(jīng)計(jì)算后，knn沒有任何更新時(shí)，便認(rèn)為沒有繼續(xù)的必要，提前終止了，這就造成了不準(zhǔn)確。

6.3 Exact search

上述的近似算法如果通過修改終止條件來變成精確算法，但是會(huì)造成大量的隨機(jī)IO讀，性能會(huì)很差。
這時(shí)候就用到了之前說的在內(nèi)存中存儲(chǔ)的所有uENV。精確算法首先用近似算法給出一組KNN，這個(gè)KNN已經(jīng)是一個(gè)很緊的上界了，之后遍歷這個(gè)內(nèi)存中的uENV list，同樣的上界剪枝法，對于沒有被prun掉的，還是和近似算法一樣，磁盤讀出序列，分別計(jì)算ED。由于內(nèi)存中的uENV list其實(shí)也是排序過的，所以IO代價(jià)有所緩解。

7. EXPERIMENTAL EVALUATION

作者用到的真實(shí)數(shù)據(jù)集有兩個(gè)，都是100M個(gè)series，每個(gè)長度256。
合成數(shù)據(jù)集用的高斯分布。

7.1 Envelope Building

首先就是索引建立的時(shí)間。一個(gè)重要的參數(shù)還是 $\gamma$ ，它決定了有多少個(gè)uENV產(chǎn)生（反比），也決定了每個(gè)uENV產(chǎn)生的時(shí)候的時(shí)間代價(jià)（正比）。

image.png

從實(shí)驗(yàn)結(jié)果一來看，索引真正建立，執(zhí)行的時(shí)間占比非常低，而且主要與 $\gamma$ ，或者說生成的uENV個(gè)數(shù)成正比；主要占用時(shí)長比較高的是計(jì)算uENV的時(shí)間。從圖一能看出來，稍稍提升下 $\gamma$ 占據(jù)query range的比例，時(shí)間就會(huì)收斂下來。

從實(shí)驗(yàn)結(jié)果二來看，不斷提升的query range對uENV的計(jì)算影響很大，文中說是線性影響，但是從圖中來看，至少是平方級別的上升，range超過300的時(shí)候，構(gòu)建實(shí)現(xiàn)超過5000s（1.5h）左右，比較緩慢了。

7.2 Exact Search Similarity Queries

改變 $\gamma$

可以非常明顯看出 $\gamma$ 增大非常有利于查詢速度，有些反直覺的是 $\gamma$ 增大導(dǎo)致uENV包含的范圍更寬會(huì)導(dǎo)致剪枝率降低，然而具體實(shí)驗(yàn)中發(fā)現(xiàn)，如果 $\gamma$ 太小，那么index中的uENV太多了，基數(shù)要比 $\gamma$ 大的時(shí)候多很多，又拖慢了查詢速度。所以 $\gamma$ 要設(shè)置偏大些，而且大的 $\gamma$ 還會(huì)使得索引大小明顯變小。
ps：作者這里還對Cmri對每種查詢長度都建立索引的方法Diss了一下，認(rèn)為它沒有擴(kuò)展性。

image.png

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

2018ICDE-ULISSE:ULtra compact Index for Variable-Length Similarity SEarch in Data Series

2018ICDE-ULISSE:ULtra compact Index for Variable-Length Similarity SEarch in Data Series

編者的總結(jié)

編者的思考

Abstract

1. Introduction

2. Related Work

3. Preliminaries