支持均勻縮放的不等長(zhǎng)時(shí)間子序列查詢(xún)方法

熊浩然，何震瀛

（1.復(fù)旦大學(xué)軟件學(xué)院，上海 200433；2.復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院， 上海 200433）

0 引言

時(shí)間序列數(shù)據(jù)是按時(shí)間順序組織的數(shù)據(jù)序列，廣泛存在于諸多領(lǐng)域，例如醫(yī)療、交通、金融等［1-3］。查詢(xún)并獲得相似的時(shí)間序列（即相似性查詢(xún)）是這些應(yīng)用中的一個(gè)基礎(chǔ)任務(wù)［4］，其效率對(duì)時(shí)序數(shù)據(jù)分析算法和流程的影響較大。為此，時(shí)間序列的相似性查詢(xún)的效率是業(yè)界長(zhǎng)久以來(lái)關(guān)注的重要問(wèn)題之一。

時(shí)間序列的相似性查詢(xún)分為全序列查詢(xún)和子序列查詢(xún)兩種［5］。全序列查詢(xún)的目標(biāo)是從一個(gè)時(shí)間序列集合中查找出與給定序列相似的序列集合；而子序列查詢(xún)旨在從一系列長(zhǎng)序列中找到與給定短序列相似的子序列集合?，F(xiàn)有大多數(shù)子序列查詢(xún)方法僅支持查找與目標(biāo)序列長(zhǎng)度相同（或接近相同）的子序列［6-9］。但在許多場(chǎng)景下，查詢(xún)序列與目標(biāo)子序列間可能存在時(shí)間維度上的伸縮（拉伸或壓縮），因此，它們的長(zhǎng)度并不一定相同。以哼唱查詢(xún)（QBH）為例，QBH 系統(tǒng)允許用戶(hù)哼唱音樂(lè)片段，并在音樂(lè)數(shù)據(jù)庫(kù)中查找與之相似的音樂(lè)片段，從而完成哼音查詢(xún)?nèi)蝿?wù)。但若用戶(hù)哼唱的速度與實(shí)際音樂(lè)片段不一致，查詢(xún)片段與實(shí)際音樂(lè)片段會(huì)存在時(shí)間維度上的差異（伸縮）。

針對(duì)此問(wèn)題，研究者引入了均勻縮放技術(shù)，通過(guò)均勻上（降）采樣的方式，將時(shí)間序列拉伸（壓縮）到不同長(zhǎng)度，從而消除序列在時(shí)間維度上的差異［10-12］。在均勻縮放的支持下，算法可查找與查詢(xún)序列長(zhǎng)度不一致但模式相似的子序列，本文將該類(lèi)查詢(xún)稱(chēng)為支持均勻縮放的不等長(zhǎng)子序列相似性查詢(xún)。除QBH 外，支持不等長(zhǎng)查詢(xún)的算法還被應(yīng)用于人類(lèi)行為識(shí)別（例如動(dòng)作、語(yǔ)音識(shí)別等）、生理監(jiān)測(cè)（例如心跳、呼吸監(jiān)測(cè)等）以及一些工業(yè)場(chǎng)景［13-15］。因此，研究者針對(duì)支持均勻縮放的不等長(zhǎng)序列查詢(xún)問(wèn)題開(kāi)展了一系列研究工作。KEOGH 等［10］針對(duì)支持均勻縮放的相似性查詢(xún)問(wèn)題，提出了理論下界距離，并結(jié)合R-樹(shù)索引，設(shè)計(jì)一種保證非漏報(bào)的高效相似性查詢(xún)算法。WAIYAWUTH 等［16］強(qiáng)調(diào)了均勻縮放與Z-標(biāo)準(zhǔn)化在相似性查詢(xún)中的重要性，并提出同時(shí)支持均勻縮放和Z-標(biāo)準(zhǔn)化的查詢(xún)算法。FU 等［17］將均勻縮放和動(dòng)態(tài)時(shí)間規(guī)整（DTW）距離結(jié)合，為其構(gòu)建理論下界距離以支持快速查詢(xún)。然而，文獻(xiàn)［10，16-17］方法僅支持全序列查詢(xún)問(wèn)題。文獻(xiàn)［11］將針對(duì)DTW 距離的優(yōu)化策略遷移到支持均勻縮放的不等長(zhǎng)查詢(xún)問(wèn)題上，提出下界距離，用于加速順序掃描的子序列查詢(xún)過(guò)程。文獻(xiàn)［12］將優(yōu)化為更緊湊的下界以提高查詢(xún)效率。然而，文獻(xiàn)［11-12］方法并未構(gòu)建索引，需要掃描整條長(zhǎng)序列以完成相似性查詢(xún)，且無(wú)法支持序列Z-標(biāo)準(zhǔn)化。此外，現(xiàn)有較為高效的子序列查詢(xún)方法，例如KV-match［7］、ULISSE［8-9］，均為長(zhǎng)序列構(gòu)建對(duì)應(yīng)的索引，減少了數(shù)據(jù)訪問(wèn)和計(jì)算開(kāi)銷(xiāo)以?xún)?yōu)化查詢(xún)效率，但它們不支持不等長(zhǎng)子序列查詢(xún)。

綜上，現(xiàn)有研究工作雖然在不等長(zhǎng)查詢(xún)問(wèn)題上取得了不錯(cuò)的效果，但在效率方面仍有提升的空間，且無(wú)法有效支持Z-標(biāo)準(zhǔn)化。為此，本文提出一種支持均勻縮放的不等長(zhǎng)子序列高效查詢(xún)方法。該方法基于ULISSE 提供的樹(shù)狀索引結(jié)構(gòu)，設(shè)計(jì)保證非漏報(bào)的下界距離，為樹(shù)狀索引結(jié)構(gòu)的剪枝提供理論保證，并結(jié)合ULISSE 索引緊湊的數(shù)據(jù)信息，提出精確K-近鄰（K-NN）查詢(xún)算法，優(yōu)化數(shù)據(jù)訪問(wèn)方式以提高查詢(xún)效率。該方法能夠同時(shí)適用于非歸一化和歸一化兩種情況。

1 問(wèn)題描述

為了全文描述的一致性，進(jìn)行如下形式化定義：

定義1（時(shí)間序列）時(shí)間序列T是按時(shí)間順序組織的數(shù)值序列，表示為T(mén)=(t1,t2,…,tn)，其中，n=|T|為序列T的長(zhǎng)度。

定義2（子序列）子序列是指時(shí)間序列中一段連續(xù)的數(shù)值組成的序列。時(shí)間序列T的子序列Ti,l表示從位置i開(kāi)始，長(zhǎng)度為l的子序列，即Ti,l=(ti,ti+1,…,ti+l-1)。

為表達(dá)簡(jiǎn)潔，本文使用S表示子序列。對(duì)于任意子序列S=(s1,s2,…,sn)，μS和σS表示序列S的均值和標(biāo)準(zhǔn)差。

定義3（Z-標(biāo)準(zhǔn)化）給定一個(gè)時(shí)間序列S=(s1,s2,…,sn)，Z-標(biāo)準(zhǔn)化后的序列表示為其中：

定義4（歐氏距離）給定兩個(gè)長(zhǎng)度為n的序列S和S'，兩者之間的歐氏距離定義為：

定義5（均勻縮放）給定一個(gè)長(zhǎng)度為n的時(shí)間序列S以及目標(biāo)長(zhǎng)度p，通過(guò)均勻縮放將S拉伸（壓縮）至長(zhǎng)度為p的序列Sp=其中：

定義6（均勻縮放距離）給定查詢(xún)Q和子序列S，兩者之間的均勻縮放距離定義為：

在處理不等長(zhǎng)序列查詢(xún)時(shí)，序列之間歐氏距離除了與序列間的相似度有關(guān)外，還受到序列長(zhǎng)度的影響，即序列越長(zhǎng)，歐氏距離趨向于越大。通常，消除長(zhǎng)度影響的做法是使用長(zhǎng)度標(biāo)準(zhǔn)化，例如用歐氏距離除以序列長(zhǎng)度來(lái)表征時(shí)間序列。LINARDI等［18］詳盡討論過(guò)該問(wèn)題。本文結(jié)合該工作中的結(jié)論，使用序列長(zhǎng)度的平方根來(lái)進(jìn)行長(zhǎng)度標(biāo)準(zhǔn)化。

定義7（歸一化均勻縮放距離）給定查詢(xún)Q和子序列S，兩者之間基于均勻縮放的歸一化距離定義為：

給定查詢(xún)先被均勻縮放為子序列等長(zhǎng)的序列Ql，且在進(jìn)行歐氏距離計(jì)算之前，兩個(gè)序列均進(jìn)行Z-標(biāo)準(zhǔn)化以保證數(shù)值維度上的統(tǒng)一，最后將歐氏距離除以長(zhǎng)度的平方根以完成長(zhǎng)度標(biāo)準(zhǔn)化。

問(wèn)題定義（精確K-近鄰查詢(xún)）給定時(shí)間序列T、考慮的長(zhǎng)度范圍[lmin,lmax]以及整數(shù)K，對(duì)于查詢(xún)序列Q，精確K-近鄰查詢(xún)將返回一個(gè)子序列集合R={S1,S2,…,SK} ?A，其中，A表示T中所有長(zhǎng)度滿(mǎn)足范圍限制的子序列集合，對(duì)于?S?R 和?S'?A-R，滿(mǎn)足D(Q,S)≤D(Q,S')。

本文考慮非歸一化以及歸一化均勻縮放距離，即Dus和Dusn。

2 預(yù)備知識(shí)

2.1 序列表征方法

分段聚合近似［19-20］（PAA）將序列S切分為等長(zhǎng)且不相交的序列片段，并分別用每個(gè)片段的均值來(lái)作為表征，從而將序列S轉(zhuǎn)換為w維的表征Vpaa(S)，其中，l為片段的長(zhǎng)度，w=S|/l。

符號(hào)聚合近似［21］（SAX）將Vpaa(S)中的w個(gè)值分別離散化為w個(gè)符號(hào)，其中離散化符號(hào)的候選集大小為c。SAX 離散化的基本思想是用c-1 個(gè)斷點(diǎn)將實(shí)數(shù)空間劃分為c個(gè)不相交區(qū)域，每個(gè)區(qū)域會(huì)有其對(duì)應(yīng)的二進(jìn)制符號(hào)。例如c=4 時(shí)，離散化符號(hào)分別為{00,01,10,11}。每個(gè)分段的均值會(huì)根據(jù)其落入的區(qū)域，離散化為對(duì)應(yīng)的二進(jìn)制符號(hào)。本文用Vsax(S)來(lái)表示序列S的SAX 表征。

可索引符號(hào)聚合近似（iSAX）遵循與SAX 相同的離散化邏輯，不同的是iSAX 允許每個(gè)分段二進(jìn)制符號(hào)的位數(shù)不相同，即不同分段的均值被離散成的符號(hào)候選集大小不固定。因此，iSAX 支持?jǐn)U充二進(jìn)制符號(hào)的位數(shù)，使得某個(gè)分段獲得更精細(xì)的離散化表征，該特性被用于建立時(shí)間序列的樹(shù)形結(jié)構(gòu)索引——iSAX 索引。類(lèi)似地，本文用Visax(S)來(lái)表示序列S的iSAX 表征。

2.2 ULISSE 索引

ULISSE 是一套以iSAX 為基礎(chǔ)，針對(duì)子序列查詢(xún)而設(shè)計(jì)的索引結(jié)構(gòu)。由于相近位置的子序列特征類(lèi)似，該索引設(shè)計(jì)了一種表征技術(shù)，有效且簡(jiǎn)潔地描述了多個(gè)不同長(zhǎng)度、位置相近的序列，并針對(duì)該表征設(shè)計(jì)了一套結(jié)構(gòu)與iSAX 索引類(lèi)似的樹(shù)形索引。為限制涉及子序列的總數(shù)量，iSAX 需要用戶(hù)提前設(shè)定子序列的長(zhǎng)度范圍，即lmin和lmax。

位置接近的子序列之間存在大量重復(fù)數(shù)值，因此，ULISSE 用統(tǒng)一的信息來(lái)總結(jié)位置相近的子序列。為獲得子序列的表征信息，ULISSE 將連續(xù)γ個(gè)開(kāi)始位置的子序列匯總為一組，并將它們的PAA 表征左對(duì)齊，每個(gè)分段PAA 數(shù)值的最大值和最小值被作為上下界信息來(lái)代表該組子序列的特征，其中，γ為用戶(hù)定義的步長(zhǎng)參數(shù)。該表征被稱(chēng)為閉包，包含上邊界UE和下邊界LE兩種統(tǒng)計(jì)信息。圖1 給出了具體示例，其中，圖1（a）示例不同開(kāi)始位置的子序列，圖1（b）將所有子序列左對(duì)齊，圖1（c）框中的區(qū)域代表該分段PAA 值的變化范圍，而LE和UE分別由這些框的下邊界和上邊界構(gòu)成。閉包的規(guī)范化表示為：

圖1 閉包構(gòu)建過(guò)程Fig.1 Construction of the envelope

其中：a表示相應(yīng)子序列在長(zhǎng)序列T中開(kāi)始數(shù)值的位置；l表示PAA 中每個(gè)分段的長(zhǎng)度。

根據(jù)定義可知，LE和UE均為lmax/l維的向量?？勺⒁獾剑瑘D1 中只給出了非Z-標(biāo)準(zhǔn)化的閉包建立過(guò)程，而要求Z-標(biāo)準(zhǔn)化時(shí)，相同開(kāi)始位置、不同長(zhǎng)度的子序列PAA 值也會(huì)變化。故ULISSE 針對(duì)Z-標(biāo)準(zhǔn)化提出了高效的閉包建立算法，其構(gòu)建結(jié)果與非歸一化類(lèi)似，在此不再贅述，其上下界分別用和表示。

此外，ULISSE 為閉包設(shè)計(jì)了一個(gè)類(lèi)似于iSAX索引的樹(shù)狀數(shù)據(jù)結(jié)構(gòu)。該索引由3 種類(lèi)型的節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)與閉包類(lèi)似，都擁有上下界信息，且每個(gè)節(jié)點(diǎn)上下界均完整覆蓋其子樹(shù)中所有子序列的PAA 表征。3 類(lèi)節(jié)點(diǎn)的特點(diǎn)為：1）根節(jié)點(diǎn)指向多個(gè)子節(jié)點(diǎn)；2）除根節(jié)點(diǎn)外的內(nèi)部節(jié)點(diǎn)均擁有2 個(gè)子節(jié)點(diǎn)；3）每個(gè)子節(jié)點(diǎn)都包含閉包表征以及其對(duì)應(yīng)子序列的位置信息，不保留原序列數(shù)據(jù)。該索引支持動(dòng)態(tài)插入序列信息，在此不再贅述。

3 不等長(zhǎng)查詢(xún)算法

3.1 下界距離

UCR suite［11］將針對(duì)DTW 問(wèn)題的解決思路遷移到均勻縮放問(wèn)題中，給出一套簡(jiǎn)單且有效的掃描加速算法，即把所有縮放后的查詢(xún)序列統(tǒng)一起來(lái)，組合構(gòu)成查詢(xún)序列的上下閉包，并利用該閉包設(shè)計(jì)下界距離，用于加速掃描查詢(xún)算法。后文構(gòu)建的下界距離需要借助到類(lèi)似思想，故此處給出該方法形式化的描述。

給定一個(gè)查詢(xún)Q以及長(zhǎng)度限制范圍[lmin,lmax]，則該查詢(xún)的下閉包和上閉包分別為L(zhǎng)和U，且滿(mǎn)足：

其中：1 ≤i≤lmin。上/下閉包是所有縮放后的查詢(xún)序列的最大值/最小值構(gòu)成的序列，圖2 給出了具體示例，其中，圖2（a）表示所有縮放后左對(duì)齊的查詢(xún)序列。

圖2 下界距離Fig.2 Lower bound distance

基于查詢(xún)閉包，可以構(gòu)建新的下界距離，用于加速均勻縮放下的不等長(zhǎng)查詢(xún)。當(dāng)考慮時(shí)間序列T中，開(kāi)始位置為s、長(zhǎng)度滿(mǎn)足限制范圍[lmin,lmax]的子序列與查詢(xún)Q的距離Dus時(shí)，可為其構(gòu)建下界距離：

其中：S表示T中以s為開(kāi)始位置的子序列；U和L分別表示查詢(xún)的上、下閉包；可被標(biāo)記為圖2（b）中陰影部分的總和。

3.1.2 本文提出的下界距離

3.1.3 PAA-iSAX 下界距離

ULISSE 的閉包信息都是以iSAX 的形式存儲(chǔ)的，因此，下界距離的計(jì)算也將以PAA 以及iSAX 表征為基礎(chǔ)。依據(jù)iSAX 的定義，文獻(xiàn)［22］提出一個(gè)iSAX 與PAA 表征之間的距離，而該距離可作為兩個(gè)序列之間歐氏距離的下界。這個(gè)性質(zhì)是兩個(gè)新下界距離設(shè)計(jì)的基礎(chǔ)，因此，本部分先引入PAA-iSAX 下界距離及其基本性質(zhì)。

令βu(?)和βl(?)分別表示iSAX 離散化符號(hào)所對(duì)應(yīng)數(shù)值范圍的最大值和最小值。給定兩個(gè)等長(zhǎng)的序列S和S'，以及分段長(zhǎng)度l，為表達(dá)簡(jiǎn)潔，假設(shè)序列長(zhǎng)度可被l整除，序列均被切分成為w段，則兩者之間的距離可定義為：

此外，根據(jù)文獻(xiàn)［23］可知該下界距離擁有以下性質(zhì)：

引理1給定兩個(gè)等長(zhǎng)序列S和S'，則有：

3.1.4 非歸一化下界距離

首先，與ULISSE 中的閉包類(lèi)似，可使用2 個(gè)向量來(lái)界定查詢(xún)的信息，分別為下閉包LQ和上閉包UQ。給定查詢(xún)Q以及長(zhǎng)度范圍[lmin,lmax]，先根據(jù)均勻縮放的定義，將查詢(xún)序列拉伸或壓縮到所有可能的長(zhǎng)度，并計(jì)算出每個(gè)伸縮后序列的PAA 表征，將所有PAA 向量左對(duì)齊后，每個(gè)維度上的最大值和最小值可構(gòu)成上閉包和下閉包2 個(gè)向量。以下給出形式化的表示：

其中：1≤i≤w；w=；l表示每個(gè)分段的長(zhǎng)度。

ULISSE 索引的閉包存儲(chǔ)了位置相近、不同長(zhǎng)度的子序列的上下界信息，再結(jié)合查詢(xún)構(gòu)成的閉包信息，可構(gòu)建下界距離。給定查詢(xún)Q，其上下界分別為UQ和LQ；給定閉包E，其上下界分別為UE和LE。Q和E之間的下界距離表示為：

類(lèi)似地，w=，其中，l表示每個(gè)分段的長(zhǎng)度。

圖3 查詢(xún)上下界及Fig.3 Lower and upper bounds of query and

性質(zhì)1給定查詢(xún)Q及其上下界UQ和LQ；給定閉包E及其上下界UE和LE。對(duì)于閉包中的任意一個(gè)子序列S，均滿(mǎn)足(Q,E) ≤Dus(Q,S)。

證明根據(jù)查詢(xún)閉包的定義，可知縮放后查詢(xún)的PAA 信息每個(gè)維度都被包含于查詢(xún)的上下界內(nèi)，即：

序列S與閉包E也有類(lèi)似的關(guān)系：

再根據(jù)iSAX 以及βu(?)和βl(?)的定義，可得到以下不等式：

故性質(zhì)1 得證。

3.1.5 歸一化下界距離

首先構(gòu)建查詢(xún)Q在歸一化條件下的上下界和。與非歸一化的方法類(lèi)似，唯一的區(qū)別是需要對(duì)縮放后的序列進(jìn)行Z-標(biāo)準(zhǔn)化操作，具體描述如下：

歸一化均勻縮放距離考慮Z-標(biāo)準(zhǔn)化的同時(shí)，引入了長(zhǎng)度標(biāo)準(zhǔn)化，因此，針對(duì)歸一化均勻縮放距離的下界距離會(huì)有所不同。給定查詢(xún)Q，其上下界分別為和；給定閉包E，其上下界分別為和Q和E之間的下界距離表示為：

類(lèi)似地，w=其中，l表示每個(gè)分段的長(zhǎng)度。

性質(zhì)2給定查詢(xún)Q及其上下界和；給定閉包E及其上下界和對(duì)于閉包中的任意一個(gè)子序列S，均滿(mǎn)足(Q,E) ≤Dusn(Q,S)。

證明該性質(zhì)的證明與性質(zhì)1 的邏輯類(lèi)似，通過(guò)查詢(xún)以及閉包的上下界定義可知：

因此，可得：

故性質(zhì)2 得證。

3.2 查詢(xún)算法

下界距離能初步界定查詢(xún)與索引中節(jié)點(diǎn)或閉包之間的距離。本部分將利用前文提及的下界距離，結(jié)合索引結(jié)構(gòu)以及存儲(chǔ)的子序列信息，給出針對(duì)均勻縮放距離的高效查詢(xún)算法，包括近似查詢(xún)算法和精確查詢(xún)算法。

3.2.1 閉包內(nèi)子序列掃描算法

在描述利用索引結(jié)構(gòu)進(jìn)行查詢(xún)的過(guò)程之前，先給出閉包內(nèi)部的子序列查詢(xún)算法。原ULISSE 算法僅能夠支持返回與查詢(xún)結(jié)果長(zhǎng)度相等的子序列，若將該算法直接運(yùn)用到支持均勻縮放的不等長(zhǎng)查詢(xún)問(wèn)題上，則最基礎(chǔ)的做法是將查詢(xún)縮放到所有可能的長(zhǎng)度，再對(duì)于每個(gè)長(zhǎng)度進(jìn)行一次等長(zhǎng)子序列查詢(xún)。但每個(gè)閉包中的子序列所在位置相鄰，會(huì)有大量的數(shù)據(jù)重疊，信息會(huì)比較相近。因此，原ULISSE 算法在解決不等長(zhǎng)查詢(xún)問(wèn)題時(shí)會(huì)造成大量重復(fù)且沒(méi)有必要的閉包以及子序列數(shù)據(jù)讀取。

借助新的下界距離，能夠統(tǒng)一判斷閉包中所有子序列與查詢(xún)的大致距離。當(dāng)下界距離大于現(xiàn)有最優(yōu)距離時(shí)，閉包存儲(chǔ)的子序列將直接被省略，不進(jìn)行下一步距離計(jì)算，且因?yàn)橄陆缇嚯x性質(zhì)的存在，該省略操作不影響查詢(xún)的正確性。當(dāng)下界距離較小時(shí)，閉包中子序列的信息將一次性取出，用于計(jì)算所有子序列與查詢(xún)的均勻縮放距離，從而減少數(shù)據(jù)重復(fù)讀取和多余磁盤(pán)開(kāi)銷(xiāo)。算法1 給出了閉包中距離計(jì)算的具體流程。

算法1閉包相似性查詢(xún)

給定閉包E后，E.a表示E中子序列在長(zhǎng)序列中的開(kāi)始位置。根據(jù)ULISSE 中閉包的定義可知，E中包含所有開(kāi)始位置位于［E.a，E.a+γ）范圍內(nèi)的所有子序列。因此，算法1 將以子序列的開(kāi)始位置作為外層循環(huán)，以該開(kāi)始位置下的不同長(zhǎng)度的子序列作為內(nèi)層循環(huán)，依次迭代計(jì)算相應(yīng)的距離。計(jì)算距離時(shí)，早停技術(shù)依然可以被使用［24］。可以注意到，一個(gè)閉包E涉及的原始序列數(shù)據(jù)僅限于E.a到E.a+γ+lmax范圍內(nèi)，因此，在算法開(kāi)始前，可統(tǒng)一將數(shù)據(jù)從磁盤(pán)加載到緩存數(shù)組中，減少磁盤(pán)訪問(wèn)量。

3.2.2 近似查詢(xún)算法

下界距離不僅能夠過(guò)濾閉包和節(jié)點(diǎn)，也能指示如何訪問(wèn)索引的順序，找到與查詢(xún)距離較為接近的子節(jié)點(diǎn)，因此，下界距離也能被使用在近似查詢(xún)中。算法2 給出了近似K-NN 查詢(xún)的過(guò)程。

算法2近似K-近鄰查詢(xún)

算法2 的基本邏輯是借助最小堆，按照下界距離從小到大訪問(wèn)對(duì)應(yīng)的節(jié)點(diǎn)。若節(jié)點(diǎn)為子節(jié)點(diǎn)時(shí)，則使用算法1 計(jì)算相應(yīng)的距離，并更新K-NN 結(jié)果R。此外，借助性質(zhì)1 和性質(zhì)2 可知，如果訪問(wèn)節(jié)點(diǎn)的下界距離大于K-NN 距離時(shí)，R數(shù)組中存儲(chǔ)的信息為精確結(jié)果，可直接結(jié)束算法，達(dá)到剪枝的效果。

3.2.3 精確K-近鄰查詢(xún)

ULISSE 在建立索引的過(guò)程中，同時(shí)維護(hù)了一個(gè)新的數(shù)據(jù)結(jié)構(gòu)，其中保存了所有的閉包信息，且根據(jù)開(kāi)始位置進(jìn)行排序，因此，使用該數(shù)據(jù)結(jié)構(gòu)可進(jìn)一步利用數(shù)據(jù)局部性原理，降低查詢(xún)開(kāi)銷(xiāo)。再結(jié)合算法1，算法3 給出了精確查詢(xún)算法的流程。

算法3精確K-近鄰查詢(xún)

當(dāng)順序掃描該數(shù)據(jù)結(jié)構(gòu)中的信息時(shí)，對(duì)應(yīng)的子序列位置也有局部性，從而可以減少磁盤(pán)訪問(wèn)的開(kāi)銷(xiāo)。算法3 開(kāi)始時(shí)先利用近似算法獲得初步結(jié)果，再依次調(diào)用算法1 獲得最終精確查詢(xún)的結(jié)果。

4 實(shí)驗(yàn)

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 實(shí)驗(yàn)數(shù)據(jù)

為探究本文方法進(jìn)行不等長(zhǎng)查詢(xún)的效率，所有的實(shí)驗(yàn)將在2 個(gè)公開(kāi)的數(shù)據(jù)集以及1 個(gè)人工合成數(shù)據(jù)集上進(jìn)行測(cè)試：1）GAP，其中包含2006—2008 年期間法國(guó)有功功率的記錄，該數(shù)據(jù)集由法國(guó)電力供應(yīng)商提供［25］；2）CAP，循環(huán)交替模式數(shù)據(jù)集，其中包含發(fā)生在非快速眼動(dòng)睡眠階段的腦電圖活動(dòng)［26］；3）SYN，人工合成數(shù)據(jù)集，利用隨機(jī)游走的方式生成的時(shí)間序列，每個(gè)數(shù)據(jù)點(diǎn)由上一個(gè)數(shù)據(jù)點(diǎn)加上隨機(jī)數(shù)值而獲得，其中隨機(jī)數(shù)從高斯分布N(0,1)中取得［9］。

實(shí)驗(yàn)中的3 個(gè)數(shù)據(jù)集長(zhǎng)度均為107，且子序列長(zhǎng)度范圍默認(rèn)設(shè)置為［256，512］。在此設(shè)置下，任意一個(gè)查詢(xún)的候選子序列數(shù)量約為109條。

針對(duì)每個(gè)數(shù)據(jù)集的查詢(xún)序列均由原序列中的子序列生成。本文隨機(jī)挑選子序列，并將其縮放為[lmin,lmax]的一個(gè)隨機(jī)長(zhǎng)度，再為縮放后的序列添加額外的高斯噪聲，以獲得最終的查詢(xún)序列。

4.1.2 基線(xiàn)方法

UCR-US［11］是支持均勻縮放距離下不等長(zhǎng)查詢(xún)的代表性方法，它改進(jìn)了UCR Suite 中的下界距離，使其適應(yīng)均勻縮放距離，需要對(duì)原始數(shù)據(jù)進(jìn)行一次順序掃描，以獲得最終查詢(xún)結(jié)果。在原論文中，縮放的長(zhǎng)度范圍隨著查詢(xún)長(zhǎng)度和預(yù)設(shè)縮放因子的變化而改變。為了保證比較的公平性，本文將縮放范圍固定為用戶(hù)自定義的范圍[lmin,lmax]。需要注意的是，該方法并不能支持歸一化均勻縮放距離，因此，本文將其作為非歸一化問(wèn)題的基線(xiàn)方法之一。

ULISSE［9］通過(guò)構(gòu)建基于iSAX 的索引，從而支持在長(zhǎng)度范圍約束內(nèi)的子序列查詢(xún)。ULISSE 支持非歸一化和歸一化兩種場(chǎng)景，能夠同時(shí)適用于本文需要解決的兩類(lèi)問(wèn)題。給定一個(gè)查詢(xún)，本文先將其縮放到所有可能的長(zhǎng)度，再逐一使用ULISSE 進(jìn)行子序列匹配。

4.2 不等長(zhǎng)查詢(xún)結(jié)果

為了驗(yàn)證本文方法的有效性，進(jìn)行3 組實(shí)驗(yàn)，分別為均勻縮放距離、歸一化均勻縮放距離下的1-NN精確查詢(xún)，以及均勻縮放距離下的K-NN 查詢(xún)。每組實(shí)驗(yàn)都分別在3 個(gè)數(shù)據(jù)集上進(jìn)行。每個(gè)實(shí)驗(yàn)均隨機(jī)生成100 條查詢(xún)序列，統(tǒng)計(jì)其平均查詢(xún)時(shí)間來(lái)體現(xiàn)查詢(xún)效率。

1）非歸一化均勻縮放距離下的1-NN 查詢(xún)效率。本文方法會(huì)使用近似查詢(xún)算法獲得近似結(jié)果，再配合閉包中的信息對(duì)來(lái)剪枝具體的距離計(jì)算，從而提高查詢(xún)效率。圖4（a）體現(xiàn)了本文方法以及UCR-US在該任務(wù)下的查詢(xún)效率。相較于UCR-US，本文方法在不同數(shù)據(jù)集上的效率提升1.67～3.59 倍，平均提升2.33 倍?？梢?jiàn)，索引的引入以及下界距離的使用可以有效減少具體的距離計(jì)算，從而提升查詢(xún)效率。

圖4 最近鄰查詢(xún)效率Fig.4 Efficiency of 1-NN query

2）歸一化均勻縮放距離下的1-NN 查詢(xún)效率。由于UCR-US 的下界距離不能支持歸一化的要求，因此該組實(shí)驗(yàn)的基線(xiàn)程序選用ULISSE 方法。圖4（b）展示了本文方法以及ULISSE 的查詢(xún)效率，其中灰色部分表示的是查詢(xún)中磁盤(pán)I/O 所占用的時(shí)間。相較于ULISSE，本文方法在不同數(shù)據(jù)集上的效率提升2.41～2.69 倍，平均提升2.51 倍。由于本文提出的下界距離考慮到了閉包中所有長(zhǎng)度的子序列，因此在計(jì)算查詢(xún)序列與閉包內(nèi)序列的具體距離時(shí)，僅需要一次磁盤(pán)讀取，從而減少了大量的磁盤(pán)I/O。在實(shí)驗(yàn)中，磁盤(pán)I/O 時(shí)間在總查詢(xún)時(shí)間中的占比平均減少29.6%。由此可知，本文方法不僅減少了計(jì)算開(kāi)銷(xiāo)，同時(shí)也節(jié)省了大部分的磁盤(pán)開(kāi)銷(xiāo)，從而獲得更多的效率提升。

3）均勻縮放距離下的K-近鄰查詢(xún)效率。圖5 展示了不同K值情況下本文算法和ULISSE 算法在GAP 數(shù)據(jù)集上的查詢(xún)效率。隨著K值增大，查詢(xún)的最終距離會(huì)越大，因此算法的過(guò)濾率會(huì)隨之下降，查詢(xún)時(shí)間會(huì)一定程度地增加，但查詢(xún)時(shí)間不會(huì)過(guò)大地波動(dòng)，基本保持在同一數(shù)量級(jí)。

圖5 GAP 數(shù)據(jù)集上的K-近鄰查詢(xún)效率Fig.5 Efficiency of K-NN query on GAP dataset

5 結(jié)束語(yǔ)

針對(duì)基于均勻縮放的不等長(zhǎng)子序列查詢(xún)問(wèn)題，本文提出一種基于索引的查詢(xún)方法，設(shè)計(jì)保證非漏報(bào)性質(zhì)的下界距離，提供索引子分支以及子節(jié)點(diǎn)中元數(shù)據(jù)的剪枝策略，減少查詢(xún)過(guò)程中的計(jì)算開(kāi)銷(xiāo)。此外，該方法利用索引中元數(shù)據(jù)具有的局部性，減少數(shù)據(jù)訪問(wèn)的次數(shù)，降低磁盤(pán)I/O 在查詢(xún)中的時(shí)間占比。在真實(shí)和人工合成數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，本文方法能有效縮短距離計(jì)算的總時(shí)間，同時(shí)降低磁盤(pán)訪問(wèn)的開(kāi)銷(xiāo)，實(shí)現(xiàn)不等長(zhǎng)子序列的高效查詢(xún)。因考慮技術(shù)闡述的簡(jiǎn)潔和清晰，本文將歐氏距離作為縮放后序列的距離度量，未來(lái)可考慮將編輯距離、DTW 距離等更加魯棒的度量方式融入到所提方法中，進(jìn)一步拓寬其適用場(chǎng)景。