劉 璐 王 鵬 汪 衛(wèi)

1(復(fù)旦大學(xué)軟件學(xué)院 上海 200120) 2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200120)

0 引 言

隨著智能設(shè)備的大量應(yīng)用，在很多應(yīng)用場(chǎng)景中會(huì)生成大型的數(shù)據(jù)集，如用戶登錄數(shù)據(jù)、設(shè)備運(yùn)行狀態(tài)數(shù)據(jù)等。這些數(shù)據(jù)在不同的時(shí)間段上會(huì)表現(xiàn)出不同的特征。在對(duì)數(shù)據(jù)進(jìn)行挖掘的過程中，常需要去發(fā)現(xiàn)屬于特定時(shí)間段的相似數(shù)據(jù)序列。以下的一個(gè)例子可以說明多時(shí)間段上相似性查詢的問題。圖1給出了一個(gè)收集了不同區(qū)域的降雨情況的數(shù)據(jù)集，橫坐標(biāo)代表時(shí)間戳，縱坐標(biāo)代表具體的降雨量的數(shù)值。考慮這樣一個(gè)問題：找出在特定時(shí)段(例如t1到t2時(shí)間段)內(nèi)與上海表現(xiàn)最相似降雨趨勢(shì)的區(qū)域。在這個(gè)問題中，查詢的時(shí)間段是固定的。一種直接的查詢方式就是通過遍歷整個(gè)數(shù)據(jù)集中t1到t2時(shí)間段內(nèi)的子序列來尋找最近鄰。但是當(dāng)數(shù)據(jù)量很大時(shí)，直接從數(shù)據(jù)集中讀取全部的序列并進(jìn)行序列相似性計(jì)算是很費(fèi)時(shí)的。為了加快查詢過程，可以給t1到t2時(shí)間段內(nèi)的子序列建立索引。每一段子序列被表示成一個(gè)摘要的值，然后根據(jù)這些摘要來建立索引。數(shù)據(jù)序列的摘要可以近似序列之間的距離，從而剪枝掉不必要的時(shí)間序列。上述的過程是在固定的時(shí)間段上創(chuàng)建索引來支持該時(shí)間段上的查詢。

圖1 多個(gè)地區(qū)降雨量

構(gòu)建單個(gè)索引以支持限制在該窗口上的查詢是可行的。但是，當(dāng)查詢窗口更改為(t3,t4)時(shí)，又需要構(gòu)建一個(gè)新索引。以圖1中的數(shù)據(jù)為例，時(shí)間序列在不同的時(shí)間段上是變化的。在時(shí)間段(t1,t2)中，北京的降雨量與上海的更為相似，但在時(shí)間段(t3,t4)內(nèi),答案應(yīng)該是杭州與上海更相似。因此，需要建立不同的索引來滿足不同的查詢窗口。顯然，如果要支持大量的查詢窗口，建立索引需要消耗的時(shí)間和空間將是巨大的。例如，對(duì)于包含長(zhǎng)度為104個(gè)時(shí)間戳的序列的數(shù)據(jù)集，可能窗口的數(shù)量約為108的數(shù)量級(jí)(考慮全部可能的時(shí)間窗口)。

目前的問題是，一些對(duì)時(shí)序數(shù)據(jù)建索引的方法只能為單個(gè)時(shí)間段(序列的一部分或整個(gè)序列)構(gòu)建索引。換句話說，對(duì)于可變窗口的查詢，這些方法需要在實(shí)際查詢每個(gè)窗口上的子序列之前為該窗口建立索引。很明顯，這既費(fèi)時(shí)又費(fèi)空間。另一方面，一些已有的可變長(zhǎng)度索引對(duì)基于窗口的查詢執(zhí)行表現(xiàn)出較低的查詢效率。因?yàn)楫?dāng)查詢受窗口而不是長(zhǎng)度限制時(shí)，它們的剪枝策略效率低下。本文提出一種構(gòu)造輕量索引的方法，達(dá)到較低的總索引代價(jià)，對(duì)于可變窗口具有高的查詢執(zhí)行性能。本文方法可以支持精確和近似最近鄰(NN)查詢以及范圍查詢。

1 關(guān)鍵概念

(1)時(shí)間窗口：如圖1所示，橫坐標(biāo)t1到t2這一段時(shí)間就稱為一個(gè)時(shí)間窗口。

(2)時(shí)序數(shù)據(jù)子序列：數(shù)據(jù)序列T={p1,p2,…,pn}是長(zhǎng)度為n的序列，其中每個(gè)數(shù)據(jù)點(diǎn)pi按時(shí)間戳的順序出現(xiàn)。數(shù)據(jù)序列在窗口w上的子序列表示為Tw，其中窗口w通常表示為(s,e)，其中s和e定義時(shí)間窗口w的開始時(shí)間點(diǎn)和結(jié)束時(shí)間點(diǎn)。

(3)時(shí)間窗口的集合：時(shí)間窗口的集合可以表示為WS={w1,w2,…,wm}。集合中的每個(gè)窗口由一個(gè)開始時(shí)間戳s和結(jié)束時(shí)間戳e表示出來。

(4)帶有窗口限制的N近鄰查詢：給定一個(gè)時(shí)間序列的集合D,給出一條查詢序列Q和一個(gè)查詢窗口w(s,e)，用規(guī)范化的歐氏距離來衡量時(shí)間序列之間的距離。查詢N近鄰的含義是：從所有限制在時(shí)間窗口w(s,e)的子序列中找到與查詢序列Qw距離最近的N條子序列。

(5)帶有窗口限制和閾值范圍的查詢：給定一個(gè)時(shí)間序列的集合D,給出一條查詢序列Q和一個(gè)查詢窗口w(s,e)以及距離閾值ε。范圍查詢的含義是：從所有限制在時(shí)間窗口w(s,e)的子序列中找到與查詢序列Q距離不大于閾值ε的所有子序列。

2 相關(guān)工作

對(duì)于時(shí)間序列距離的衡量，目前已經(jīng)有很多文獻(xiàn)提出距離計(jì)算的方法。給定兩個(gè)標(biāo)準(zhǔn)化的時(shí)間序列Q和T，一個(gè)相似的函數(shù)dist測(cè)量Q和T之間的距離，用dist(Q,T)表示兩條序列之間的距離。目前主要的序列距離計(jì)算方式包括歐氏距離(ED)[1]、DTW[2]、最長(zhǎng)公共子序列(LCSS)[3]等。在這項(xiàng)工作中，使用ED作為距離測(cè)量。ED是時(shí)間序列中最常見的相似性度量，因?yàn)樗芎?jiǎn)單且便于計(jì)算。對(duì)于距離測(cè)量的詳細(xì)信息，可以參考文獻(xiàn)[4]。

為計(jì)算在某個(gè)窗口上的相似子序列，直接掃描所有子序列進(jìn)行查詢非常耗時(shí)。之前很多工作提出了許多計(jì)算序列摘要方法，使用子序列的摘要值對(duì)子序列進(jìn)行剪枝，例如：離散傅里葉變換[5]、奇異值分解、哈爾變換[6]、APCA[7]、分段均值(PAA)[8]和SAX[9]等。在不同的應(yīng)用中通常需要根據(jù)剪枝的能力對(duì)摘要進(jìn)行選擇。

為了加快查詢速度，現(xiàn)有方法通常會(huì)根據(jù)序列的摘要?jiǎng)?chuàng)建索引。索引構(gòu)建方法可分為兩種樣式：自頂向下索引和自底向上索引。自頂向下的方式構(gòu)造索引會(huì)從根節(jié)點(diǎn)開始把序列放到節(jié)點(diǎn)中[10-12]，當(dāng)節(jié)點(diǎn)容量滿了之后就將節(jié)點(diǎn)進(jìn)行拆分。這種方法會(huì)導(dǎo)致許多小的隨機(jī)I/O存儲(chǔ)，從而降低索引構(gòu)建速度。同時(shí)，由于節(jié)點(diǎn)大小不固定，整個(gè)指數(shù)結(jié)構(gòu)是較難描述的。另一種自底向上的構(gòu)造索引方式，例如Coconut[13]，在索引構(gòu)建之前對(duì)數(shù)據(jù)序列進(jìn)行排序，從而避免存儲(chǔ)空間的再次分配。因此，它以更快的方式構(gòu)建索引，而無須拆分節(jié)點(diǎn)。一旦序列被排好序，序列的摘要和序列指針就會(huì)直接被刷新到磁盤。

除了單獨(dú)對(duì)每個(gè)時(shí)間窗口建立索引，目前有一些把多個(gè)窗口的索引壓縮到一起的方法[14-16]。但是這些索引壓縮的方法對(duì)基于窗口的查詢表現(xiàn)出較低剪枝能力，因?yàn)檫@些索引壓縮的方式?jīng)]有充分考慮到索引的特征和相似程度，導(dǎo)致壓縮后的索引比較粗糙。另一方面，這些方法通常只是把鄰近的窗口上的索引壓縮到一起，而并不能把非相鄰窗口的索引進(jìn)行壓縮。

總之，不管是單窗口的索引還是已有的可變窗口的索引，都不能有效地用于基于窗口的相似性搜索問題。這項(xiàng)工作提出了利用不同查詢窗口的索引的相似性，對(duì)索引的時(shí)間空間開銷進(jìn)行優(yōu)化。

3 方法描述

3.1 方法目標(biāo)和方法概述

對(duì)于查詢窗口較多的時(shí)候，為每個(gè)時(shí)間窗口分別建立索引是很低效的方式。對(duì)于所有需要建立索引的時(shí)間窗口，本文的基本思想是，如果兩個(gè)窗口上構(gòu)建的索引具有類似的索引結(jié)構(gòu)，則這兩個(gè)窗口的索引是相似的。通過把相似的窗口聚類到一起，提取出相似的索引中冗余的部分，以達(dá)到索引壓縮的效果。

3.2 窗口索引的相似度

這里主要考慮對(duì)于自底向上索引結(jié)構(gòu)的壓縮。正如前文講到過的，自底向上的索引結(jié)構(gòu)通常根據(jù)時(shí)間序列排序的情況來組織序列，基于排序來構(gòu)建索引。也就是說，窗口上時(shí)間序列的排序情況決定了窗口的索引結(jié)構(gòu)。這一特征有助于比較不同索引之間的相似程度。

序列和窗口之間的關(guān)系可以由圖2體現(xiàn)出來。對(duì)于圖2中的4個(gè)窗口w1-w4,12條序列T1-T12，每一條序列都可以在4個(gè)窗口上切出4條不同的子序列。每段子序列可以計(jì)算出一個(gè)摘要值(例如摘要可以定義為一段子序列中數(shù)據(jù)的均值)。由于在不同的窗口上計(jì)算出的摘要值不同，子序列的排序情況不同，從而不同窗口的索引結(jié)構(gòu)就不同。在實(shí)現(xiàn)方法的時(shí)候，本文使用的序列排序方式參考文獻(xiàn)[13]。

圖2 不同窗口上序列的相對(duì)位置

下面說明如何根據(jù)窗口內(nèi)序列排序的情況來計(jì)算窗口間的距離。這里舉例了兩個(gè)窗口w5和w6。表1中序列的順序就是子序列的兩個(gè)窗口上的排序情況，w5和w6上序列順序略有不同。直接拿排序情況比較兩個(gè)窗口的相似度復(fù)雜度會(huì)較高。事實(shí)上需要比較的是兩個(gè)窗口上每個(gè)排序區(qū)間包含的序列的差異。

表1中列舉了一個(gè)簡(jiǎn)單的例子。把排序后的12條序列劃分成3個(gè)長(zhǎng)度為4的排序區(qū)間：1～4、5～8、9～12。對(duì)w5和w6兩個(gè)窗口而言，每個(gè)窗口上的12條子序列分別放到了如表1的排序區(qū)間里。那么通過比較每個(gè)排序區(qū)間，就能比較出兩個(gè)窗口的差異。

表1 不同窗口上的排序情況

對(duì)表1兩個(gè)窗口的表示，并不能直觀地進(jìn)行計(jì)算。為了數(shù)字化地表示出每個(gè)排序范圍里分布了哪些子序列，本文把序列按照它們的編號(hào)又進(jìn)行了分組。若設(shè)置編號(hào)分組大小為3，那么編號(hào)為前3的序列依次為T1、T2、T3就被分到第一個(gè)編號(hào)分組，T4、T5、T6屬于第二個(gè)編號(hào)分組，以此類推第三編號(hào)分組中的序列是T7、T8、T9，第四個(gè)編號(hào)分組是T10、T11、T12。然后就可以通過計(jì)數(shù)的方式表示序列的分布情況。如表2所示，把每個(gè)排序區(qū)間都總結(jié)成4個(gè)數(shù)值(這里數(shù)值的個(gè)數(shù)等于編號(hào)分組的數(shù)量)，這4個(gè)數(shù)值分別表示各個(gè)編號(hào)分組內(nèi)的序列有多少個(gè)出現(xiàn)在了當(dāng)前的排序區(qū)間。例如，w5中的排序1～4的序列中有3個(gè)序列屬于第一個(gè)編號(hào)分組，分別為T1、T2、T3，而T4屬于第二個(gè)編號(hào)分組。第三和第四個(gè)編號(hào)分組的序列沒有出現(xiàn)在排序區(qū)間1～4中，所以計(jì)數(shù)分別為3、1、0、0。w5中排序?yàn)?到8的序列中沒有第一個(gè)編號(hào)分組中的序列，有2個(gè)(T5和T6)屬于第二個(gè)編號(hào)分組的序列，第三個(gè)編號(hào)分組的序列(T7)和第四個(gè)編號(hào)分組的序列(T11)各有一個(gè)，所以計(jì)數(shù)分別為0、2、1、1。w6的序列分布情況計(jì)算是同理的。這樣就統(tǒng)計(jì)出了各個(gè)窗口上序列的分布情況?？梢钥吹诫m然w5和w6的序列排序不完全相同，但是表示出來的序列分布情況是相同的。這就意味著本文方法根據(jù)索引結(jié)構(gòu)的實(shí)際情況比較索引之間的相似程度，而不是僅僅依賴于精確的序列排序，這樣的計(jì)算方法更有利于找到相似的索引，并且計(jì)算復(fù)雜度也相對(duì)低。

表2 窗口的表示

把窗口的每個(gè)排序區(qū)間的表示拼起來表示成一個(gè)向量，例如w5表示為<3,1,0,0,0,2,1,1,0,0,2,2>。進(jìn)而，窗口間的距離就可以用窗口間的歐氏距離來計(jì)算。

3.3 窗口聚類

將每個(gè)窗口表示成了上述的向量形式，然后用向量間的歐氏距離來度量不同窗口的索引間的距離，根據(jù)這個(gè)距離來對(duì)窗口進(jìn)行聚類?；谝陨系拇翱谙蛄亢痛翱诰嚯x定義，本文使用k-means[17]對(duì)窗口進(jìn)行聚類。參數(shù)k用來控制聚類的個(gè)數(shù)。聚類過程首先選擇k個(gè)窗口的向量作為初始k個(gè)聚類中心：

(1)聚類更新：給每個(gè)窗口計(jì)算它的向量到k個(gè)中心向量的歐氏距離，把每個(gè)窗口分到距離最近的那個(gè)聚類。

(2)重新計(jì)算聚類中心：對(duì)更新之后的每個(gè)聚類中所有向量計(jì)算，計(jì)算這些向量的均值作為新的聚類中心。

這樣就得到了k個(gè)窗口的聚類結(jié)果。接下來的建立索引的過程是逐一在這k個(gè)聚類上分別進(jìn)行的。

3.4 索引結(jié)構(gòu)和構(gòu)建方法

對(duì)于每個(gè)窗口的聚類，只選擇一個(gè)代表窗口，同一聚類中的其他窗口被稱作附屬窗口。本文選擇離聚類中心最近的窗口作為代表窗口。下面分別介紹如何為代表窗口和附屬窗口創(chuàng)建輕量級(jí)索引。

(1)代表窗口：代表窗口索引的構(gòu)建遵循常規(guī)的自底向上構(gòu)建索引的方式，首先對(duì)數(shù)據(jù)集中的所有時(shí)間序列切分出代表窗口內(nèi)的子序列，然后對(duì)子序列進(jìn)行排序[13]。指定索引中節(jié)點(diǎn)大小的參數(shù)，把排好序的序列依次放到節(jié)點(diǎn)中，當(dāng)?shù)谝粋€(gè)節(jié)點(diǎn)裝滿后，就繼續(xù)裝第二個(gè)節(jié)點(diǎn)，以此類推。同時(shí)每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)摘要用來描述節(jié)點(diǎn)中包含的時(shí)間序列的信息。每個(gè)節(jié)點(diǎn)的摘要就作為最終該節(jié)點(diǎn)的索引信息。

(2)附屬窗口：在構(gòu)造索引的步驟中，附屬窗口內(nèi)的子序列不需要再進(jìn)行排序，而是使用該窗口所在聚類的代表窗口同樣的序列排序。也就是說附屬窗口的每個(gè)節(jié)點(diǎn)指向的序列集合與它所在聚類的代表窗口相同。附屬窗口同樣需要計(jì)算每個(gè)節(jié)點(diǎn)的摘要，作為描述節(jié)點(diǎn)的索引。由于窗口是不同的，節(jié)點(diǎn)的摘要計(jì)算出來也是不同的。

也就是說，每個(gè)聚類中只維護(hù)一次序列的排序情況，而不是給每個(gè)窗口都維護(hù)依次排序。由于只維護(hù)代表窗口的排序，這樣很大程度上節(jié)省了索引占用的開銷。這個(gè)聚類中唯一維護(hù)的排序稱為聚類的排序。每個(gè)聚類的排序和聚類里所有窗口的對(duì)應(yīng)關(guān)系如圖3所示。聚類C1中只包含了一份排序信息，聚類中的兩個(gè)窗口依次根據(jù)每個(gè)排序區(qū)間的序列構(gòu)建節(jié)點(diǎn)的摘要。每個(gè)窗口的節(jié)點(diǎn)摘要和排序的對(duì)應(yīng)關(guān)系如圖3所示。

圖3 索引結(jié)構(gòu)圖

(3)節(jié)點(diǎn)摘要的計(jì)算：無論是代表窗口還是附屬窗口，每個(gè)節(jié)點(diǎn)的摘要其實(shí)總結(jié)了該節(jié)點(diǎn)指向的所有子序列。由于排序中只保留了序列的編號(hào)，在計(jì)算不同窗口上的節(jié)點(diǎn)摘要的時(shí)候，只需要把序列對(duì)應(yīng)到不同窗口上的子序列然后計(jì)算即可。節(jié)點(diǎn)摘要可以用來計(jì)算任意一條查詢序列到節(jié)點(diǎn)指向的全部序列的距離下界。

例如，給定一個(gè)序列子集S={T1,T2,T3,T4}，每個(gè)子序列可以表示成x段的SAX值[5]，這里舉例x=3。那么指向子集S的節(jié)點(diǎn)摘要就由兩個(gè)長(zhǎng)度為3的下界和上界構(gòu)成。下界用向量L來表示，上界由向量U來表示。另外，用SAXi(Tj)來表示序列Tj的SAX值的第i段，其中：i=1,2,3；j=1,2,3,4。那么L和U可以描述為：

式中:參數(shù)i表示L和U的第i個(gè)分段。有了這樣的節(jié)點(diǎn)摘要，就可以明確計(jì)算出任意一條查詢序列到一個(gè)節(jié)點(diǎn)指向的全部序列的距離下界，這樣就能保證在查詢的過程中不去訪問那些一定不包含最終結(jié)果的序列。文獻(xiàn)[16]給出了定理來說明如何計(jì)算這個(gè)距離下界。

4 基于索引的查詢

本文的索引支持以下三種查詢：近似N近鄰查詢、精確N近鄰查詢和帶閾值范圍的查詢。對(duì)于一個(gè)查詢Q和窗口w，Q到一個(gè)節(jié)點(diǎn)中所有序列的下界距離可以由公式計(jì)算出來，參考文獻(xiàn)[16]。

4.1 近似N近鄰查詢

經(jīng)典的基于索引的查詢方式[13]在計(jì)算近似解的時(shí)候，通常優(yōu)先訪問最有可能包含結(jié)果的節(jié)點(diǎn)。類似地，CBI選擇Q和節(jié)點(diǎn)的摘要之間下邊距離最小的節(jié)點(diǎn)摘要。鎖定節(jié)點(diǎn)摘要之后，可以定位到摘要指向的一段排序中包含的所有序列，然后計(jì)算Q到這些序列的確切歐氏距離，選出距離最小的N條就完成近似N近鄰的查詢。

4.2 精確N近鄰查詢

在精確N近鄰查詢中，首先使用近似查詢的答案作為初始的最優(yōu)解(BSF)。然后用BSF來檢查查詢窗口w的每個(gè)節(jié)點(diǎn)摘要。對(duì)于距離下界大于BSF的節(jié)點(diǎn)摘要可以直接剪枝掉，不再繼續(xù)訪問該節(jié)點(diǎn)中的序列。對(duì)于滿足距離下界的節(jié)點(diǎn)摘要，定位到該摘要指向的一段排序中的全部序列，逐一計(jì)算Q到節(jié)點(diǎn)中每條序列的距離，并更新最優(yōu)距離。完成對(duì)所有節(jié)點(diǎn)摘要的檢查后，就得到了精確N近鄰查詢的解。

4.3 帶閾值限制的查詢

由于每個(gè)節(jié)點(diǎn)都維護(hù)了一個(gè)可以提供距離下界的摘要，當(dāng)查詢帶有閾值限制時(shí)，直接檢查每個(gè)節(jié)點(diǎn)摘要和Q的距離下界，如果節(jié)點(diǎn)摘要的距離大于閾值，則不再繼續(xù)訪問當(dāng)前節(jié)點(diǎn)指向的序列。反之，如果當(dāng)前節(jié)點(diǎn)的距離下界小于閾值要求，則逐條檢查節(jié)點(diǎn)指向序列和查詢Q的精確歐氏距離是否滿足閾值，滿足閾值的序列即加入到結(jié)果集合中。

5 實(shí)驗(yàn)與結(jié)果分析

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

所有實(shí)驗(yàn)均在16 GB DDR4內(nèi)存的Intel i7-7700k CPU上執(zhí)行。本文測(cè)試了以下數(shù)據(jù)集：

(1)真實(shí)數(shù)據(jù)集使用的是一個(gè)濕度數(shù)據(jù)集，其中包含1998年1月至2018年12月從美國(guó)9 115個(gè)不同站點(diǎn)收集的濕度測(cè)量數(shù)據(jù)[18]。該數(shù)據(jù)集的總大小為8 GB，包含約2×109個(gè)浮點(diǎn)數(shù)，數(shù)值范圍為[0,100]。

(2)生成數(shù)據(jù)集合成時(shí)間序列是由隨機(jī)游走時(shí)間序列、高斯時(shí)間序列和混合正弦時(shí)間序列三種時(shí)間序列組合而成的。生成一個(gè)4 GB的合成數(shù)據(jù)，其中包含10萬個(gè)數(shù)據(jù)序列，長(zhǎng)度為10 000，數(shù)據(jù)數(shù)值范圍為[-5,5]。

本文實(shí)驗(yàn)的所有方法都是使用Java語言實(shí)現(xiàn)的。

5.2 索引的性能

為了評(píng)估CBI創(chuàng)建索引的性能，進(jìn)行了聚類效率的研究。如圖4所示，3 200個(gè)聚類過程需要大約30 min。聚類幾乎是CBI中唯一耗時(shí)的過程。這說明CBI建立索引所需要的時(shí)間開銷較小。

圖4 CBI聚類時(shí)間

圖5顯示了CBI在多個(gè)窗口的索引建立方面如何優(yōu)于Coconut方法。從平均每個(gè)索引建立的時(shí)間開銷來看，本文的索引在基于窗口的索引時(shí)間上是優(yōu)于普通的單索引構(gòu)造方式的。

圖5 平均每個(gè)窗口上索引的構(gòu)造時(shí)間

空間使用分析：當(dāng)索引參數(shù)固定時(shí)，CBI和Coconut消耗空間大小分別都是固定的。以4 GB的生成數(shù)據(jù)集為例，假設(shè)每個(gè)序列由16段的SAX表示，索引的節(jié)點(diǎn)大小設(shè)置為200，單個(gè)窗口的Coconut索引的最終大小為7 MB。CBI單個(gè)壓縮索引的大小為32 KB。很明顯，CBI索引大小比Coconut小得多。需要構(gòu)建的基于窗口的索引越多，CBI節(jié)省的空間就越多。

5.3 查詢性能

通過與Coconut索引和子序列匹配方法KV-match[19]進(jìn)行比較，評(píng)估CBI的查詢性能。由于這兩個(gè)對(duì)比算法本身的原因，它們并不完全支持文中列出的這三種查詢。Coconut支持精確和近似的N近鄰查詢，KV-match支持閾值范圍查詢。

(1)N近鄰查詢：比較了CBI與Coconut的剪枝效率，在生成數(shù)據(jù)集上選擇查詢窗口長(zhǎng)度為1 000的整數(shù)倍，并對(duì)每個(gè)窗口運(yùn)行10個(gè)隨機(jī)查詢。平均剪枝效率如圖6所示，圖中的數(shù)據(jù)比較了不同聚類情況下CBI的效率，橫坐標(biāo)CBI括號(hào)里的數(shù)字代表聚類個(gè)數(shù)。剪枝率定義為查詢過程中從磁盤上讀取的序列的數(shù)量比上總的序列數(shù)。6 400個(gè)聚類的CBI的剪枝率為91%，略低于Coconut的93.6%。對(duì)于CBI，構(gòu)建的聚類數(shù)越多，剪枝效率越高。

圖6 剪枝率

查詢時(shí)間如圖7所示。隨機(jī)選擇長(zhǎng)度為1 000的窗口，將查詢時(shí)間與Coconut進(jìn)行比較。除了CBI和Coconut之外，還對(duì)比了直接暴力搜索的方法運(yùn)行查詢的時(shí)間開銷，該方法直接掃描磁盤上的數(shù)據(jù)集并計(jì)算查詢與所有數(shù)據(jù)系列之間的標(biāo)準(zhǔn)化歐氏距離。結(jié)論是，CBI在節(jié)省空間開銷的同時(shí)，可以很好地保證查詢效率，平衡了直接搜索的查詢方式和單索引Coconut的不足。

圖7 不同方法的查詢時(shí)間

(2)帶閾值限制的范圍查詢：由于Coconut索引的結(jié)構(gòu)不能支持閾值限制查詢，通過選擇可變長(zhǎng)度的索引KV-match來驗(yàn)證CBI的閾值查詢性能。在生成的數(shù)據(jù)集上測(cè)試了各種范圍閾值，并使用1 000的查詢窗口長(zhǎng)度。圖8給出了KV-match在變量窗口查詢上執(zhí)行的剪枝效率很弱。即使對(duì)于一個(gè)小的閾值3，KV-match也需要計(jì)算64 846個(gè)數(shù)據(jù)序列的精確歐氏距離，導(dǎo)致剪枝能力低于36%。CBI在范圍查詢中表現(xiàn)出較好的剪枝效率。

圖8 不同閾值下的剪枝效率

6 結(jié) 語

本文論述了目前其他一些方法的索引不適合可變窗口查詢的問題，提出一種壓縮的自底向上索引(CBI)方法。本文從索引的原理、索引結(jié)構(gòu)、索引構(gòu)造方法等多個(gè)方面對(duì)提出的方法進(jìn)行了闡述。實(shí)驗(yàn)結(jié)果表明，CBI能夠高效、準(zhǔn)確地回答給定數(shù)據(jù)集上的基于窗口的查詢，比目前已有的方法在索引開銷和查詢效率方面有較大的改進(jìn)。下一步將考慮如何進(jìn)一步壓縮CBI索引，進(jìn)一步減少索引開銷并繼續(xù)提升索引查詢效率。