DSI:一種基于動(dòng)態(tài)分段的時(shí)間序列查詢(xún)索引

周騎駿,王 鵬,汪 衛(wèi)

(復(fù)旦大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,上海 201203)

0 概述

時(shí)間序列數(shù)據(jù)[1-2]是指隨著時(shí)間進(jìn)行變化的一系列數(shù)據(jù),通常存在于日志數(shù)據(jù)中,例如某天的CPU、硬盤(pán)使用率、某個(gè)地區(qū)一年的溫度等。這些數(shù)據(jù)由物聯(lián)網(wǎng)中的傳感器進(jìn)行采集,并上傳至服務(wù)器作為每天的日志數(shù)據(jù)。數(shù)據(jù)科學(xué)家將其作為基礎(chǔ)數(shù)據(jù),查詢(xún)并分析該數(shù)據(jù)從而得出結(jié)果來(lái)進(jìn)一步優(yōu)化目標(biāo)。時(shí)間序列數(shù)據(jù)具有數(shù)據(jù)格式單一、數(shù)據(jù)種類(lèi)復(fù)雜、數(shù)據(jù)之間關(guān)聯(lián)性強(qiáng)等特點(diǎn)。關(guān)于時(shí)間序列的查詢(xún)通常需要構(gòu)建索引,索引構(gòu)建方法主要有B+樹(shù)[3-4]、布隆過(guò)濾器[5]、solr搜索服務(wù)器[6]。對(duì)于時(shí)間序列而言,大部分時(shí)間上相鄰的時(shí)間序列數(shù)據(jù)具有較強(qiáng)的關(guān)聯(lián)性,單條數(shù)據(jù)的索引不適用于時(shí)間序列數(shù)據(jù)。文獻(xiàn)[7]在無(wú)序的基于LSM樹(shù)[8-9]數(shù)據(jù)存儲(chǔ)上對(duì)觀測(cè)的時(shí)間序列數(shù)據(jù)進(jìn)行存儲(chǔ)索引,將時(shí)間序列數(shù)據(jù)按照時(shí)間劃分成一塊塊固定長(zhǎng)度的分段并且進(jìn)行查詢(xún)。該方法可以使用較小的代價(jià)就能完成對(duì)時(shí)間序列數(shù)據(jù)的快速訪(fǎng)問(wèn),但由于其是固定分段,因此沒(méi)有考慮時(shí)間序列本身的特征,缺乏靈活性,在進(jìn)行范圍查詢(xún)時(shí),獲取的無(wú)關(guān)數(shù)據(jù)量較多,查詢(xún)效率較低。

本文提出一種基于動(dòng)態(tài)分段的時(shí)間序列索引DSI。該索引將一條時(shí)間序列根據(jù)自身數(shù)據(jù)特點(diǎn),設(shè)置相應(yīng)的限制參數(shù)進(jìn)行分段,形成數(shù)據(jù)長(zhǎng)度不同的分段。對(duì)于分段查詢(xún),使用區(qū)間樹(shù)對(duì)分段塊進(jìn)行搜索并通過(guò)主鍵查詢(xún)數(shù)據(jù)。

1 相關(guān)知識(shí)

1.1 時(shí)間序列的基本定義

時(shí)間序列T是采集到的時(shí)間長(zhǎng)度為m的數(shù)據(jù),可表示為T(mén)={t1,t2,…,tm-1,tm},按照一定的時(shí)間間隔采集時(shí)間序列中的數(shù)據(jù)t1、t2,相鄰點(diǎn)的時(shí)間差值相等。

1.2 時(shí)間序列的局部性

時(shí)間序列數(shù)據(jù)存儲(chǔ)一般是以采集數(shù)據(jù)的時(shí)間作為主鍵,依據(jù)采集時(shí)間進(jìn)行排序,相鄰數(shù)據(jù)具有一定的關(guān)聯(lián)性。因?yàn)槭褂谜咦x取某一時(shí)間數(shù)據(jù)后,很有可能繼續(xù)讀取相鄰時(shí)間段的數(shù)據(jù),所以讀取時(shí)間序列數(shù)據(jù)時(shí)不只是讀取一條數(shù)據(jù),而是連續(xù)讀取一段時(shí)間序列數(shù)據(jù),為創(chuàng)建分段索引提供了理論依據(jù)。

2 DSI索引

2.1 索引查詢(xún)框架

在數(shù)據(jù)查詢(xún)時(shí),首先向索引查詢(xún)框架(如圖1所示)輸入請(qǐng)求,索引查詢(xún)框架根據(jù)請(qǐng)求確定目標(biāo)數(shù)據(jù)塊,然后返回目標(biāo)索引塊的行鍵,最后用戶(hù)根據(jù)行鍵存儲(chǔ)系統(tǒng)中查詢(xún)的目標(biāo)數(shù)據(jù)。

圖1 索引查詢(xún)框架

2.2 數(shù)據(jù)塊的建立依據(jù)

DSI是根據(jù)時(shí)間序列數(shù)據(jù)目標(biāo)字段的值進(jìn)行動(dòng)態(tài)切分的一種索引。相對(duì)于將數(shù)據(jù)劃分為相同長(zhǎng)度的數(shù)據(jù)塊索引來(lái)說(shuō),DSI根據(jù)數(shù)據(jù)值之間的關(guān)系進(jìn)行切分及索引,能夠減少無(wú)效數(shù)據(jù)的讀取,提升讀取效率。在圖2中,兩條虛線(xiàn)之間的數(shù)據(jù)為一個(gè)數(shù)據(jù)段。每個(gè)數(shù)據(jù)段包含數(shù)據(jù)的個(gè)數(shù)不同,算法根據(jù)時(shí)間序列數(shù)據(jù)的特性,在數(shù)據(jù)點(diǎn)之間差異大、數(shù)據(jù)波動(dòng)大的地方,例如一條時(shí)間序列的波峰和波谷區(qū)間,減少相應(yīng)的段長(zhǎng)度。對(duì)于數(shù)據(jù)波動(dòng)較少的地方增加相應(yīng)的段長(zhǎng)度,同時(shí)對(duì)于數(shù)據(jù)頻度較小,即數(shù)據(jù)出現(xiàn)次數(shù)較小的數(shù)據(jù)段減少相應(yīng)的數(shù)據(jù)段長(zhǎng)度,從而提升有效數(shù)據(jù)的讀取量。

圖2 索引數(shù)據(jù)塊的動(dòng)態(tài)劃分

2.3 DSI 建立

2.3.1 DSI結(jié)構(gòu)

DSI索引主要包含索引塊和區(qū)間樹(shù)兩部分。由于時(shí)間序列的數(shù)據(jù)值隨時(shí)間的變化而變化,因此根據(jù)時(shí)間將存儲(chǔ)在存儲(chǔ)系統(tǒng)中的每個(gè)時(shí)間序列段劃分為一個(gè)個(gè)更小的數(shù)據(jù)段。

R={[r1,r2),[r2,r3),…,[rm-1,rm)}

(1)

其中,R為一個(gè)索引塊集合,rm表示時(shí)間序列中第m個(gè)點(diǎn)的主鍵,[rm-1,rm)定義為左閉右開(kāi)的區(qū)間。當(dāng)用戶(hù)進(jìn)行范圍查詢(xún)時(shí),給出一個(gè)查詢(xún)區(qū)間。將查詢(xún)區(qū)間和索引序列段上信息進(jìn)行對(duì)比,如果符合條件,則表明時(shí)間序列數(shù)據(jù)段是用戶(hù)所需的數(shù)據(jù),因此提取整個(gè)數(shù)據(jù)塊。圖3為索引整體結(jié)構(gòu)。在存儲(chǔ)系統(tǒng)中,根據(jù)主鍵查詢(xún)存儲(chǔ)系統(tǒng)中的數(shù)據(jù),將時(shí)間序列根據(jù)其自身特點(diǎn)劃分為一個(gè)個(gè)邏輯數(shù)據(jù)塊。在索引層中,為每一個(gè)邏輯數(shù)據(jù)塊創(chuàng)建一個(gè)相應(yīng)的索引塊,該塊包含了描述邏輯數(shù)據(jù)塊的信息,然后使用區(qū)間樹(shù)獲取索引塊。

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

2.3.2 索引塊的描述

一條索引塊表示的數(shù)據(jù)塊可能包含成百上千條數(shù)據(jù),也可能包含幾十條數(shù)據(jù),根據(jù)時(shí)間序列數(shù)據(jù)的特點(diǎn)確定,因此需找到一個(gè)合適的方法對(duì)這些數(shù)據(jù)進(jìn)行切分。對(duì)于每一個(gè)目標(biāo)數(shù)據(jù)塊,把目標(biāo)塊中的最大值和最小值作為索引的關(guān)鍵信息。這樣既能節(jié)省索引空間,又能在一定程度上保持查詢(xún)準(zhǔn)確率。因此,對(duì)于每一個(gè)索引塊,可將其看作[min,max]區(qū)間。對(duì)于區(qū)間查詢(xún)來(lái)說(shuō),區(qū)間查詢(xún)的左右端點(diǎn)構(gòu)成的區(qū)間與索引塊區(qū)間相交,該塊是需要查詢(xún)的數(shù)據(jù)塊。同時(shí),由于描述信息簡(jiǎn)單,因此當(dāng)有大量數(shù)據(jù)插入時(shí),索引建立速度也較快。表1詳細(xì)介紹了索引中各字段的數(shù)據(jù)構(gòu)成,其中tolerance字段表示該索引代表的數(shù)據(jù)塊中數(shù)據(jù)值的差值,該差值用于下文中索引塊的生成。

2.3.3 索引塊的生成

根據(jù)上文描述可知,數(shù)據(jù)之間的差值越小,代表數(shù)據(jù)之間的波動(dòng)越小。數(shù)據(jù)之間的差值越大,數(shù)據(jù)值之間的波動(dòng)越大,則應(yīng)該切分成不同的數(shù)據(jù)段。但對(duì)于每一類(lèi)時(shí)間序列數(shù)據(jù),由于數(shù)量之間的差異,因此對(duì)于不同的時(shí)間序列數(shù)據(jù)塊的切分不同,需要用戶(hù)指定差值E。同時(shí),根據(jù)差值E確保每個(gè)數(shù)據(jù)段中的數(shù)據(jù)之間的差值小于差值E。

推論1對(duì)于一個(gè)普通的時(shí)間序列t[i:j],要保證時(shí)間序列t[i:j]不被切分,只需保證該時(shí)間序列數(shù)據(jù)的最大值和最小值的差值小于E即可,證明如下:

range[i:j]=maxt[k]-mint[k]≤E,i≤k≤j

(2)

綜上所述,確保每個(gè)數(shù)據(jù)段中數(shù)據(jù)之間的差值小于E,只需找到數(shù)據(jù)段的最大值和最小值進(jìn)行切分。同時(shí),借助于APCA[10-11]思想,動(dòng)態(tài)劃分時(shí)間序列,基于此,本文提出一種不定長(zhǎng)的時(shí)間序列分塊劃分算法。

算法1時(shí)間序列分塊劃分算法

輸入時(shí)間序列T,基準(zhǔn)差值E>0,差值級(jí)別count

輸出索引集合indexList

1.indexList ← {}

2.初始化minValue,maxValue,lastTol

3.計(jì)算T的標(biāo)準(zhǔn)差和均值mean,stdv

4.map← splitTolerance(mean,E,stdv,count)

5.for each data t[i]in T do

6.tol← min(map.get(t[i]),lastTol)

7.If max(maxValue,t[i])-min(minValue,t[i])>tol

//生成索引塊并加入到索引集合中

8.indexBlock←generateIndexBlock()

9.indexList.add(indexBlock)

10.重置minValue,maxValue,lastTol

11.else

12.minValue←min(minValue,t[i])

13.maxValue←max(maxValue,t[i])

14.lastTol←tol

15.end if

16.end for

17.return indexList

由算法1可知,該算法的輸入為時(shí)間序列T,用戶(hù)的輸入差值E以及用戶(hù)劃分的差值級(jí)別count,用戶(hù)對(duì)于不同數(shù)值大小的數(shù)據(jù)切分差值也不同。輸出為切分的塊,即索引集合。首先初始化各參數(shù)值,其中,minValue代表當(dāng)前段的最小值,maxValue代表當(dāng)前段的最大值,lastTol代表上一個(gè)相鄰的索引(第1行、第2行)。然后計(jì)算出時(shí)間序列的數(shù)據(jù)均值mean以及標(biāo)準(zhǔn)差stdv,便于下文不同數(shù)值數(shù)據(jù)進(jìn)行級(jí)別劃分賦予相應(yīng)差值。在得到均值及標(biāo)準(zhǔn)差后,根據(jù)均值、標(biāo)準(zhǔn)差以及基準(zhǔn)差值生成相應(yīng)的差值項(xiàng)(第3行)。函數(shù)splitTolerance根據(jù)不同數(shù)據(jù)值產(chǎn)生不同的差值,由一個(gè)鍵值對(duì)形式的集合map進(jìn)行保存。遍歷時(shí)間序列T中的每項(xiàng)值t[i],首先獲取當(dāng)前t[i]在map中對(duì)應(yīng)的差值,然后和上條數(shù)據(jù)的差值lastTol對(duì)比并取較小值。根據(jù)推論1,用當(dāng)前段的最大值減去最小值確定是否超過(guò)當(dāng)前差值,如果超過(guò)差值則進(jìn)行索引塊的建立(第4行)。接著為下一個(gè)索引塊重置minValue、maxValue、lastTol(第5行～第10行)。反之,保留當(dāng)前差值,即賦值給lastTol,同時(shí)將minValue、maxValue和t[i]比較更新最小值和最大值(第12行～第14行)。

splitTolerance是根據(jù)差值進(jìn)行切分的函數(shù),輸入?yún)?shù)為差值級(jí)別count、均值mean、標(biāo)準(zhǔn)差stdv及基準(zhǔn)差值E。在現(xiàn)實(shí)數(shù)據(jù)中,存在異常數(shù)據(jù)及極端數(shù)據(jù)。拉伊達(dá)法則[12]表明均值mean范圍上下的3個(gè)標(biāo)準(zhǔn)差stdv的數(shù)據(jù)范圍內(nèi)能夠涵蓋接近99%的數(shù)據(jù),同時(shí)數(shù)據(jù)數(shù)值和mean值越接近,數(shù)據(jù)頻度越大。圖4為一個(gè)count值為2的區(qū)間劃分結(jié)果。首先設(shè)立一個(gè)以mean值為中心,范圍為[mean-3stdv,mean+3stdv]的區(qū)間。count等于2代表將[mean,mean+3stdv]平均分成兩份,從而產(chǎn)生2個(gè)區(qū)間[mean,A]和[A,mean+3stdv],同一區(qū)間內(nèi)的數(shù)據(jù)差值一樣。距離中心值越近的區(qū)間,該區(qū)間的差值越大,區(qū)間[mean,A]和[A,mean+3stdv]產(chǎn)生了2個(gè)差值K1,K2。[mean,A]區(qū)間距離mean值更近,因此差值K1大于K2。K1值為基準(zhǔn)差值E,K2值為E/2。對(duì)于[mean+3tdv,max]特殊區(qū)間中點(diǎn)差值,則使用相鄰區(qū)間的差值,在本例中為K2的值。同理,如果count為n,則在n個(gè)切分區(qū)間中的第i(K1≤i≤n)個(gè)區(qū)間差值數(shù)據(jù)為E/i,[mean+3tdv,max]的區(qū)間數(shù)據(jù)為E/n。因?yàn)閙ean值左邊部分與右邊部分是對(duì)稱(chēng)的,所以不再贅述。

圖4 數(shù)據(jù)差值判斷

2.4 區(qū)間樹(shù)查詢(xún)

2.4.1 區(qū)間樹(shù)結(jié)構(gòu)

本文主要利用區(qū)間樹(shù)進(jìn)行索引塊的快速查找,區(qū)間樹(shù)是由動(dòng)態(tài)集合維護(hù)的紅黑樹(shù),是一種自平衡的二叉樹(shù),主要用于對(duì)區(qū)間數(shù)據(jù)的查詢(xún),區(qū)間樹(shù)由紅色節(jié)點(diǎn)和黑色節(jié)點(diǎn)構(gòu)成,因此對(duì)n個(gè)節(jié)點(diǎn)區(qū)間的插入和刪除都能在O(lgn)時(shí)間內(nèi)完成。區(qū)間樹(shù)的結(jié)構(gòu)如表2所示。區(qū)間樹(shù)每個(gè)節(jié)點(diǎn)主要由五部分構(gòu)成:左右端點(diǎn)left和right,left是一個(gè)實(shí)數(shù)值,right是一個(gè)鍵值對(duì)形式的集合;左右孩子區(qū)間樹(shù)節(jié)點(diǎn)指針node_L和node_R,分別指向左右孩子區(qū)間樹(shù)節(jié)點(diǎn);NodeMax,代表當(dāng)前節(jié)點(diǎn)及子樹(shù)節(jié)點(diǎn)的左右端點(diǎn)的最大值。在表2中,第2條數(shù)據(jù)id為2,左端點(diǎn)數(shù)據(jù)為8,右端點(diǎn)是一個(gè)鍵值對(duì)集合,包含有關(guān)鍵字為9及關(guān)鍵字為20的鍵值對(duì)元素,同時(shí)左子節(jié)點(diǎn)是id為3的節(jié)點(diǎn),右子節(jié)點(diǎn)不存在。當(dāng)前節(jié)點(diǎn)以及子樹(shù)的最大值NodeMax為20。

表2 區(qū)間樹(shù)結(jié)構(gòu)

2.4.2 區(qū)間樹(shù)建立

在建立區(qū)間樹(shù)時(shí),需先了解如何將一個(gè)索引塊節(jié)點(diǎn)轉(zhuǎn)化為一個(gè)區(qū)間樹(shù)節(jié)點(diǎn)。在查詢(xún)區(qū)間樹(shù)時(shí),主要是通過(guò)比較區(qū)間樹(shù)節(jié)點(diǎn)的左端點(diǎn)與右端點(diǎn)進(jìn)行查詢(xún),因此當(dāng)構(gòu)造區(qū)間樹(shù)時(shí),將獲得的索引塊的min值作為區(qū)間樹(shù)的左端點(diǎn)left,max值作為區(qū)間樹(shù)的右端點(diǎn)right的一部分。由于區(qū)間樹(shù)可能出現(xiàn)左右端點(diǎn)一致的情況,造成很多的冗余節(jié)點(diǎn),因此將區(qū)間樹(shù)的右端點(diǎn)轉(zhuǎn)化為一個(gè)有序集合。需要注意的是,該有序集合是一個(gè)鍵值對(duì)形式的集合,鍵是每一個(gè)索引塊的max值,而值是一個(gè)鏈表形式的集合list,list中存儲(chǔ)的是索引塊的rowkey_start起始主鍵和rowkey_end結(jié)束主鍵等關(guān)鍵信息,因此左端點(diǎn)相同的數(shù)據(jù)都在同一個(gè)區(qū)間樹(shù)節(jié)點(diǎn)中。圖5為索引塊到區(qū)間樹(shù)節(jié)點(diǎn)的轉(zhuǎn)化表示,對(duì)于一個(gè)blockid為10的索引塊,索引塊的min值為8,max值為20,將min值作為區(qū)間樹(shù)節(jié)點(diǎn)的左端點(diǎn),max值作為區(qū)間樹(shù)節(jié)點(diǎn)的右端點(diǎn),同時(shí)NodeMax值為max值。

圖5 索引塊到區(qū)間樹(shù)的轉(zhuǎn)化過(guò)程

相對(duì)于傳統(tǒng)將每一個(gè)索引塊都獨(dú)立為一個(gè)樹(shù)節(jié)點(diǎn)的方法,區(qū)間樹(shù)查詢(xún)將左端點(diǎn)相同的索引塊進(jìn)行融合,根據(jù)NodeMax剪枝以及右端點(diǎn)有序的特點(diǎn),減少查詢(xún)目標(biāo)數(shù)據(jù)時(shí)的比較次數(shù)。在區(qū)間樹(shù)的建立過(guò)程中,輸入已劃分好的索引塊,每個(gè)索引塊都有一個(gè)min值和max值,只需將索引塊轉(zhuǎn)化為區(qū)間的節(jié)點(diǎn)數(shù)據(jù)即可。首先初始化一個(gè)區(qū)間樹(shù),并獲取樹(shù)的根節(jié)點(diǎn),然后初始化一個(gè)臨時(shí)節(jié)點(diǎn)。對(duì)于索引塊集合的每一索引塊,先將其轉(zhuǎn)化為區(qū)間樹(shù)節(jié)點(diǎn)。其中索引塊的max值為區(qū)間節(jié)點(diǎn)的NodeMax值,將根節(jié)點(diǎn)的NodeMax值和當(dāng)前的NodeMax進(jìn)行對(duì)比,取兩者較大的值來(lái)更新根節(jié)點(diǎn)的NodeMax值。接著使用當(dāng)前插入節(jié)點(diǎn)和根節(jié)點(diǎn)的左端點(diǎn)進(jìn)行比較,如果左端點(diǎn)小于根節(jié)點(diǎn)的左端點(diǎn),則繼續(xù)和根節(jié)點(diǎn)的左子樹(shù)進(jìn)行比較。如果2個(gè)左端點(diǎn)相等則將該節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)的存儲(chǔ)集合中,并取2個(gè)節(jié)點(diǎn)的NodeMax值的較大值為新的NodeMax值,表示這2個(gè)節(jié)點(diǎn)共用一個(gè)樹(shù)節(jié)點(diǎn);否則與根節(jié)點(diǎn)的右子樹(shù)節(jié)點(diǎn)進(jìn)行比較。如果不存在left值相同的節(jié)點(diǎn),則在葉子節(jié)點(diǎn)中創(chuàng)建一個(gè)新的區(qū)間節(jié)點(diǎn)。最后根據(jù)紅黑樹(shù)的性質(zhì)進(jìn)行樹(shù)旋轉(zhuǎn)操作來(lái)保持整個(gè)樹(shù)的平衡。旋轉(zhuǎn)操作的詳細(xì)過(guò)程可參見(jiàn)文獻(xiàn)[13-14]。

圖6為索引塊節(jié)點(diǎn)在區(qū)間樹(shù)中的插入過(guò)程,其中右半部分的區(qū)間樹(shù)根據(jù)表2構(gòu)建而成。在每一個(gè)區(qū)間樹(shù)節(jié)點(diǎn)中,虛線(xiàn)上半部分代表了該節(jié)點(diǎn)的左右端點(diǎn),虛線(xiàn)下半部分表示該節(jié)點(diǎn)的NodeMax值。將blockid為11的索引塊轉(zhuǎn)化為left為8、right鍵值對(duì)集合中鍵為17的一個(gè)區(qū)間樹(shù)節(jié)點(diǎn),NodeMax的值為17。由于區(qū)間樹(shù)以左端點(diǎn)為關(guān)鍵字進(jìn)行排序,因此插入節(jié)點(diǎn)的left值(8)和根節(jié)點(diǎn)left值(10)進(jìn)行比較,由于插入節(jié)點(diǎn)的left值小于根節(jié)點(diǎn)left值,因此進(jìn)一步遍歷根節(jié)點(diǎn)的左子節(jié)點(diǎn)。在遍歷左子節(jié)點(diǎn)時(shí),發(fā)現(xiàn)有l(wèi)eft為8的區(qū)間節(jié)點(diǎn),便插入該節(jié)點(diǎn)中。由于右端點(diǎn)right是一個(gè)有序集合,其中key包含9和20等數(shù)值,在對(duì)右端點(diǎn)鍵為17的數(shù)據(jù)進(jìn)行插入時(shí),只需找到第一個(gè)大于17的數(shù)據(jù)插入到該數(shù)據(jù)中。在本例中,插入到鍵為20的元素前。

圖6 區(qū)間樹(shù)的插入過(guò)程

2.5 索引查詢(xún)處理

2.5.1 索引查詢(xún)算法

索引塊存在于區(qū)間樹(shù)節(jié)點(diǎn)中,先從區(qū)間樹(shù)中找出索引塊。對(duì)于區(qū)間樹(shù)的查詢(xún)[15-17],除了圖7中兩種區(qū)間樹(shù)查詢(xún)沒(méi)有命中的情況,即查詢(xún)區(qū)間的左端點(diǎn)大于區(qū)間節(jié)點(diǎn)的右端點(diǎn)和區(qū)間節(jié)點(diǎn)的左端點(diǎn)小于查詢(xún)節(jié)點(diǎn)的右端點(diǎn),其余都是需要查詢(xún)的目標(biāo)線(xiàn)段。在圖7中,細(xì)實(shí)線(xiàn)為查詢(xún)的目標(biāo)區(qū)間,粗實(shí)線(xiàn)為區(qū)間樹(shù)中的區(qū)間。

圖7 區(qū)間樹(shù)查詢(xún)不命中的情況

在獲得目標(biāo)區(qū)間后,遍歷區(qū)間樹(shù)中的每個(gè)節(jié)點(diǎn),給出索引塊的查詢(xún)算法,其中輸入為區(qū)間樹(shù)根節(jié)點(diǎn)t、查詢(xún)區(qū)間[left,right]、區(qū)間集list。

算法2索引查詢(xún)算法RecursiveSearch

//區(qū)間樹(shù)左端點(diǎn)不大于查詢(xún)區(qū)間右端點(diǎn)兩者才有交集

1.if t !=NIL and t.leftpoint<=right

//返回區(qū)間樹(shù)右端點(diǎn)第一個(gè)大于查詢(xún)區(qū)間左端點(diǎn)的位置

2.start<-findFirst(t.rightpoint,left)

//將該位置開(kāi)始一直到有序集合末尾數(shù)據(jù)都加入list

3.list.add(t.rightpoint,start)

4.end if

5.leftchild<-t.leftchild;rightchild<-t.rightchild

6.if leftchild!=NIL and

7.leftchild.NodeMax>=left

8.RecursiveSearch(leftchild,left,right,list)

9.end if

10.if rightchild!=NIL and

11.rightchild.NodeMax>=left

12.RecursiveSearch(rightchild,left,right,list)

13.end if

該算法是一個(gè)遞歸算法,輸入為區(qū)間樹(shù)根節(jié)點(diǎn)t,查詢(xún)區(qū)間[left,right]以及用于存放數(shù)據(jù)的集合list,主要是對(duì)區(qū)間樹(shù)中的節(jié)點(diǎn)進(jìn)行遍歷,先判斷該節(jié)點(diǎn)是否存在圖7(a)的情況,即查詢(xún)的區(qū)間右端點(diǎn)right小于區(qū)間樹(shù)節(jié)點(diǎn)的左端點(diǎn)t.leftpoint。如果滿(mǎn)足該情況,則可以把當(dāng)前節(jié)點(diǎn)排除(第1行)。對(duì)于圖7(b)的情況,因?yàn)閰^(qū)間樹(shù)右端點(diǎn)t.rightpoint是一個(gè)集合,則只要判斷區(qū)間樹(shù)的右端點(diǎn)集合t.rightpoint中是否有數(shù)據(jù)大于查詢(xún)區(qū)間的左端點(diǎn)left即可,因?yàn)閰^(qū)間樹(shù)的右端點(diǎn)集合t.rightpoint依次遞增,只需找到右端集合t.rightpoint中第一個(gè)大于查詢(xún)區(qū)間的左端點(diǎn)left即可。調(diào)用findFirst函數(shù)找到右端點(diǎn)集合元素key中第一個(gè)大于查詢(xún)區(qū)間左端點(diǎn)left,并返回鍵值對(duì)序號(hào)start(第2行)。由于區(qū)間樹(shù)的右端點(diǎn)t.rightpoint中的key集合是有序的,從start開(kāi)始的位置一直到集合末尾右端點(diǎn)集合元素中的key都大于查詢(xún)區(qū)間左端點(diǎn)left,這些集合元素都滿(mǎn)足查詢(xún)要求,因此從start位置開(kāi)始到集合末尾位置的數(shù)據(jù)都加入到list(第3行)。由于無(wú)需比較每一個(gè)節(jié)點(diǎn)集合中所有數(shù)據(jù),因此在一定程度上提高了查詢(xún)效率。接著判斷左子節(jié)點(diǎn)leftchild的NodeMax值是否大于查詢(xún)區(qū)間左端點(diǎn)left,左子節(jié)點(diǎn)leftchild的NodeMax代表了當(dāng)前左子樹(shù)的節(jié)點(diǎn)最大值。如果NodeMax不大于查詢(xún)區(qū)間左端點(diǎn)left,則滿(mǎn)足圖7(b)的情況,可進(jìn)一步進(jìn)行剪枝(第6行～第9行)。如果不滿(mǎn)足,則繼續(xù)以相同方式遍歷右子節(jié)點(diǎn)rightchild(第10行～第13行)?？傮w來(lái)說(shuō),通過(guò)多個(gè)索引段的融合排序以及NodeMax剪枝,可使整個(gè)區(qū)間樹(shù)查詢(xún)算法效率得到進(jìn)一步提升。本質(zhì)上該算法是對(duì)二叉樹(shù)的遍歷,二叉樹(shù)的遍歷時(shí)間復(fù)雜度為O(n),總的時(shí)間復(fù)雜度為O(n),n為區(qū)間節(jié)點(diǎn)個(gè)數(shù)。由于區(qū)間樹(shù)節(jié)點(diǎn)具有NodeMax屬性,同時(shí)區(qū)間樹(shù)節(jié)點(diǎn)的右端點(diǎn)是有序的,因此在進(jìn)行查詢(xún)時(shí)一定程度上減少了查詢(xún)比較次數(shù),最終的時(shí)間復(fù)雜度應(yīng)遠(yuǎn)小于O(n),空間復(fù)雜度為O(1)。

2.5.2 查詢(xún)結(jié)果優(yōu)化

對(duì)于一個(gè)區(qū)間查詢(xún)請(qǐng)求,可能返回很多的索引段。因此需要進(jìn)一步縮減結(jié)果,文獻(xiàn)[18-19]使用層次聚類(lèi)算法將多個(gè)結(jié)果集合進(jìn)行聚類(lèi)進(jìn)一步減少結(jié)果數(shù)。圖8展示了將查詢(xún)出的時(shí)間序列結(jié)果進(jìn)行層次聚類(lèi)的過(guò)程,候選集為4個(gè)聚類(lèi),需要聚合成2個(gè)聚類(lèi)。左邊數(shù)字為時(shí)間序列塊,右邊數(shù)字為候選集結(jié)果聚類(lèi)r。首先計(jì)算所有結(jié)果集中兩兩聚類(lèi)之間的距離。找出聚類(lèi)集中距離最小的2個(gè)聚類(lèi)集r1、r2,距離最小代表2個(gè)聚類(lèi)融合引入的無(wú)關(guān)數(shù)據(jù)量最少。將r1、r2進(jìn)行融合變成r5,接著進(jìn)一步融合,計(jì)算r3、r4、r5中距離最小的2個(gè)聚類(lèi),因?yàn)閞3、r4融合需要引入序號(hào)為5、6的不相關(guān)時(shí)間序列數(shù)據(jù)段,而r5、r6融合需要僅引入序號(hào)為3的不相關(guān)時(shí)間序列數(shù)據(jù)段,代價(jià)較小,因此將r5、r3融合成r6。

圖8 層次聚類(lèi)過(guò)程

算法3展示了層次聚類(lèi)的具體過(guò)程,輸入數(shù)據(jù)為結(jié)果集合list,目標(biāo)聚類(lèi)數(shù)count,先將list中的每一項(xiàng)轉(zhuǎn)化為一個(gè)cluster(第1行),然后對(duì)cluster中的每?jī)身?xiàng)進(jìn)行兩兩距離計(jì)算,由于是對(duì)區(qū)間進(jìn)行層次聚合,因此選取的距離函數(shù)是找到2個(gè)聚類(lèi)中的區(qū)間最小距離(第2行、第3行)。在每次合并后,就減少一個(gè)聚類(lèi)個(gè)數(shù),如果聚類(lèi)個(gè)數(shù)達(dá)到要求則返回;否則繼續(xù)進(jìn)行下一輪聚類(lèi)(第4行)?？傮w來(lái)說(shuō),本文方法是以犧牲一定的查詢(xún)精準(zhǔn)度來(lái)獲取更少的結(jié)果集,其每次只保存最小距離值,因此空間復(fù)雜度為O(1),而需要計(jì)算出兩兩聚類(lèi)的距離,時(shí)間復(fù)雜度為O(n3),n為當(dāng)前聚類(lèi)個(gè)數(shù)。

算法3層次聚類(lèi)算法

輸入結(jié)果集list、聚類(lèi)個(gè)數(shù)count

輸出目標(biāo)聚類(lèi)個(gè)數(shù)listclusters

1.將list中的每一項(xiàng)轉(zhuǎn)化成為一個(gè)cluster,得到cluster的集合listclusters

2.對(duì)listclusters中的每一項(xiàng),兩兩計(jì)算距離

3.找到距離最小的2個(gè)聚類(lèi),合并聚類(lèi)

4.判斷當(dāng)前cluster個(gè)數(shù)是否小于count,若大于count則返回步驟2,若小于count則進(jìn)行步驟5

5.返回結(jié)果集listclusters

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

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)在單臺(tái)計(jì)算機(jī)上運(yùn)行,處理器為Intel Core i7-4710 2.5 GHz,內(nèi)存大小為24 GB,操作系統(tǒng)為64位Windows 7,JDK版本為1.8.0_152。

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

實(shí)驗(yàn)數(shù)據(jù)主要來(lái)自于CMOP[20]觀測(cè)數(shù)據(jù)和股票數(shù)據(jù)2個(gè)數(shù)據(jù)集。CMOP觀測(cè)數(shù)據(jù)來(lái)自于傳感器測(cè)量出的溫度數(shù)據(jù),數(shù)據(jù)時(shí)間范圍為2008年12月1日至2011年11月30日,數(shù)據(jù)量約為3 000萬(wàn),溫度數(shù)據(jù)平緩、波動(dòng)較小。股票數(shù)據(jù)主要是來(lái)源于滬深股市300支股票的一檔掛單數(shù)據(jù)(通過(guò)電腦進(jìn)行買(mǎi)賣(mài)的股票數(shù)據(jù)),數(shù)據(jù)時(shí)間范圍為2013年3月1日至2013年12月31日,數(shù)據(jù)量約為600萬(wàn),該數(shù)據(jù)相對(duì)溫度數(shù)據(jù)震蕩、波動(dòng)較大。本文對(duì)比方法為基于固定分段的時(shí)間序列查詢(xún)索引CRI[7]。

3.3 實(shí)驗(yàn)結(jié)果

3.3.1 相同量級(jí)數(shù)據(jù)集下的數(shù)據(jù)查詢(xún)效果

為保證實(shí)驗(yàn)公平性,在索引塊數(shù)量一致的情況下進(jìn)行相同數(shù)據(jù)的查詢(xún)。DSI和CRI的查詢(xún)效率如圖9所示。橫坐標(biāo)為進(jìn)行查詢(xún)的數(shù)據(jù)區(qū)間實(shí)際包含數(shù)據(jù)的條數(shù),縱坐標(biāo)為查詢(xún)到的結(jié)果集的數(shù)據(jù)量。在CMOP數(shù)據(jù)集中,對(duì)實(shí)際包含數(shù)據(jù)量為30、300、3 000的數(shù)據(jù)區(qū)間進(jìn)行查詢(xún),最終返回索引所標(biāo)記的數(shù)據(jù)量。由于數(shù)據(jù)查詢(xún)是以塊的方式進(jìn)行,因此查詢(xún)到的數(shù)據(jù)總量越少,代表查詢(xún)到的數(shù)據(jù)包含的無(wú)關(guān)數(shù)據(jù)量越少,查詢(xún)精度越高。由圖9可以看出,DSI效果優(yōu)于CRI,且由于股票數(shù)據(jù)的波動(dòng)較大,因此對(duì)此目標(biāo)查詢(xún)區(qū)間,DSI能夠有效識(shí)別并劃分區(qū)間。

圖9 相同量級(jí)數(shù)據(jù)集下查詢(xún)效率對(duì)比

3.3.2 不同量級(jí)數(shù)據(jù)集下的數(shù)據(jù)查詢(xún)效果

在DSI和CRI產(chǎn)生的索引塊數(shù)量一致的情況下,圖10展示了不同數(shù)據(jù)總量下的查詢(xún)效率,在CMOP數(shù)據(jù)集和股票數(shù)據(jù)集中,查詢(xún)數(shù)據(jù)量是總數(shù)的10-4,對(duì)于總的數(shù)據(jù)量為3 000萬(wàn)的數(shù)據(jù)集,查詢(xún)數(shù)據(jù)量為10-4,即查詢(xún)包含3 000條的數(shù)據(jù)區(qū)間,由此可知,查詢(xún)到的總數(shù)據(jù)量小的索引的無(wú)關(guān)數(shù)據(jù)少,效率高。可以看出,DSI仍?xún)?yōu)于CRI,主要原因在于DSI是根據(jù)目標(biāo)查詢(xún)數(shù)據(jù)的分布來(lái)動(dòng)態(tài)切分?jǐn)?shù)據(jù)。在該過(guò)程中,DSI關(guān)注了數(shù)據(jù)分布,而CRI是靜態(tài)劃分,僅記錄最大值和最小值,因此在查詢(xún)時(shí)經(jīng)常訪(fǎng)問(wèn)到包含極端值的塊,從而導(dǎo)致查詢(xún)到的無(wú)關(guān)數(shù)據(jù)較多,數(shù)據(jù)量增加。對(duì)于DSI動(dòng)態(tài)查詢(xún),極端值根據(jù)差值被切分成不同的段,從而不影響正常的數(shù)據(jù)查詢(xún)。

圖10 不同量級(jí)數(shù)據(jù)集下的查詢(xún)效率對(duì)比

3.3.3 數(shù)據(jù)差值對(duì)查詢(xún)結(jié)果的影響

圖11為對(duì)3 000萬(wàn)CMOP觀測(cè)數(shù)據(jù)、600萬(wàn)股票數(shù)據(jù)的查詢(xún)結(jié)果。每一類(lèi)數(shù)據(jù)都是調(diào)整不同差值后,對(duì)各自相同數(shù)據(jù)區(qū)間進(jìn)行查詢(xún)。對(duì)于股票數(shù)據(jù)而言,當(dāng)差值數(shù)據(jù)為20、40、60、80時(shí)，對(duì)應(yīng)的數(shù)據(jù)總塊數(shù)分別為1.39×106、6.9×105、3.5×105、1.9×105。隨著差值的增加,數(shù)據(jù)總塊數(shù)逐漸減少,但查詢(xún)數(shù)據(jù)逐漸增多。隨著差值的減少,數(shù)據(jù)總塊數(shù)增加,在查詢(xún)目標(biāo)塊數(shù)時(shí)需要花費(fèi)更多時(shí)間,但查詢(xún)無(wú)關(guān)數(shù)據(jù)少。對(duì)于較平緩的CMOP觀測(cè)數(shù)據(jù),當(dāng)差值數(shù)據(jù)為0.1、0.5、1.1、1.5時(shí)，對(duì)應(yīng)的數(shù)據(jù)總塊數(shù)分別為2.79×106、4.8×105、1.6×105、1.1×105。隨著數(shù)據(jù)總塊數(shù)的減少，查詢(xún)出的數(shù)據(jù)也相對(duì)減少。

圖11 數(shù)據(jù)差值對(duì)查詢(xún)結(jié)果的影響

3.3.4 差值等級(jí)對(duì)查詢(xún)結(jié)果的影響

圖12是不同差值等級(jí)對(duì)查詢(xún)結(jié)果的影響。對(duì)于CMOP感測(cè)數(shù)據(jù)而言，當(dāng)差值等級(jí)為1、5、10、15時(shí)，對(duì)應(yīng)的數(shù)據(jù)總塊數(shù)分別為2.5×104、2.6×105、7.5×105、1.09×106；對(duì)于股票數(shù)據(jù)而言，當(dāng)差值等級(jí)為1、5、10、1.5時(shí)，對(duì)應(yīng)的數(shù)據(jù)總塊數(shù)分別為3.8×105、8.7×105、1.43×106、1.65×106。由此可知,隨著差值等級(jí)值的變大,產(chǎn)生的索引塊數(shù)會(huì)變多。在差值逐漸變大的過(guò)程中,早期對(duì)提升數(shù)據(jù)查詢(xún)精準(zhǔn)度有一定的影響,隨著差值增大到一定程度時(shí),例如CMOP數(shù)據(jù)和股票數(shù)據(jù)差值在15時(shí),索引塊數(shù)變多,但查詢(xún)精度并沒(méi)有明顯提升,因此選取一個(gè)合適的差值等級(jí)至關(guān)重要。

圖12 差值等級(jí)對(duì)查詢(xún)結(jié)果的影響

3.3.5 區(qū)間樹(shù)查詢(xún)效率實(shí)驗(yàn)

表3是區(qū)間樹(shù)查詢(xún)的效率結(jié)果。第2行～第4行是溫度數(shù)據(jù)的區(qū)間查詢(xún)情況。對(duì)于第2行數(shù)據(jù)來(lái)說(shuō),生成總區(qū)間段是67 967個(gè),由于利用紅黑樹(shù)節(jié)點(diǎn)的left值進(jìn)行排序,相同left值會(huì)加入到同一節(jié)點(diǎn),因此生成的節(jié)點(diǎn)數(shù)大幅減少,同時(shí),每個(gè)樹(shù)的右邊節(jié)點(diǎn)是一個(gè)根據(jù)right值排好的鍵值對(duì)集合,在查詢(xún)時(shí)無(wú)需對(duì)區(qū)間樹(shù)節(jié)點(diǎn)right值集合中的每一個(gè)值進(jìn)行判斷,只需找到樹(shù)集合中大于查詢(xún)區(qū)間的左端點(diǎn)的第一個(gè)值即可,后續(xù)節(jié)點(diǎn)不用判別是否相交,便可直接加入。同時(shí),每個(gè)節(jié)點(diǎn)還有NodeMax值,通過(guò)NodeMax值算法能在一定程度上減少查詢(xún)時(shí)與區(qū)間樹(shù)節(jié)點(diǎn)的比較次數(shù)。在67 957個(gè)區(qū)間中,查詢(xún)180個(gè)區(qū)間,只需與區(qū)間樹(shù)節(jié)點(diǎn)進(jìn)行13 523次比較。對(duì)于股票數(shù)據(jù),由于數(shù)據(jù)波動(dòng)大但范圍小,因此生成的節(jié)點(diǎn)數(shù)比較少。由以上結(jié)果可知,區(qū)間樹(shù)查詢(xún)?cè)谝欢ǔ潭葴p少了區(qū)間遍歷的次數(shù)。

表3 區(qū)間樹(shù)查詢(xún)效率

3.3.6 層次聚類(lèi)算法對(duì)查詢(xún)結(jié)果的影響

圖13為層次聚類(lèi)算法對(duì)查詢(xún)結(jié)果的影響,顯示了3 000萬(wàn)CMOP數(shù)據(jù)集和600萬(wàn)股票數(shù)據(jù)集對(duì)于10 000條數(shù)據(jù)及200條數(shù)據(jù)的查詢(xún)情況。由此可知,隨著聚類(lèi)數(shù)的增加,查詢(xún)結(jié)果集的冗余數(shù)逐漸變少,但對(duì)于用戶(hù)來(lái)說(shuō),結(jié)果集變多,將耗費(fèi)更多的時(shí)間去查看其中結(jié)果,因此用戶(hù)需根據(jù)不同數(shù)據(jù)的特點(diǎn)選擇合適的結(jié)果集。

圖13 層次聚類(lèi)算法對(duì)查詢(xún)結(jié)果的影響

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

本文針對(duì)時(shí)間數(shù)據(jù)的局部性特點(diǎn),提出基于動(dòng)態(tài)分段的時(shí)間序列值查詢(xún)索引,用戶(hù)根據(jù)數(shù)據(jù)特點(diǎn)通過(guò)動(dòng)態(tài)分段提升查詢(xún)效果,并使用層次聚類(lèi)算法解決結(jié)果集過(guò)多的問(wèn)題。實(shí)驗(yàn)結(jié)果表明,本文索引的查詢(xún)效率優(yōu)于傳統(tǒng)時(shí)間序列索引。但層次聚類(lèi)需要用戶(hù)手動(dòng)設(shè)置,因此下一步可將層次聚類(lèi)的參數(shù)改為自動(dòng)設(shè)置,減少查詢(xún)?nèi)哂?同時(shí)根據(jù)不同時(shí)間序列數(shù)據(jù)的特點(diǎn)調(diào)整輔助參數(shù),進(jìn)一步提升查詢(xún)性能。