基于線性散列索引的時間序列查詢方法研究

戴珂

摘 要：隨著信息化的發(fā)展，大量的數據被產生。在新產生的數據中，時間序列數據是一種重要的數據類型，而對該類數據進行高效的查詢處理成為了當前研究的熱點。本文針對線性散列的索引機制，提出了一種新型的時間序列的查詢處理方法，以降低索引創(chuàng)建時間和提高查詢效率。實驗證明，本方法中的線性散列索引，在創(chuàng)建時的時間耗費有所下降。在查詢階段采用K近鄰與下界距離相結合的方法，能有效地過濾掉多余的結果，提高了時間序列查詢處理的效率和精確度。

關鍵詞：時間序列；線性散列；K-近鄰；下界距離

中圖分類號：TP391 文獻標識碼：A

Abstract：With the development of information science，more and more data is generated through different applications.Time series is an important data type，and the research on how to query time series data efficiently has drawn more and more attention.This paper proposes a new time series query processing method based on linear hash，aiming to reduce the index construction time and improve the query efficiency.The experiment results show that the index construction time has been reduced to some extent.Through the combined method of the K-nearest neighbor and the lower bounding distance in the query phase，redundant results can be effectively filtered，which improves the efficiency and accuracy of the time series query.

Keywords：time series；linear hash；K-nearest neighbor；lower bounding distance

1 引言（Introduction）

時間序列（Time Series）指同一指標的數值按其先后發(fā)生的時間順序排列而成的數列，它作為時態(tài)數據的一種特殊形式出現在許多領域，如金融的股票交易價格、醫(yī)學的心腦電圖、氣象的溫濕度走勢、企業(yè)的產銷走勢等。時間序列的表示是針對時間序列的結構復雜而采取的，將時間序列進行變形的技術；時間序列的索引是針對如何進行高效存儲，以及快速查詢時間序列的技術。

由于時間序列的數據量大和復雜結構，為表示和索引提出了難題?，F有的檢索技術，處理大數據時經常會耗費大量的時間。其相似性度量也往往不夠準確。國內外研究學者提供了許多相似性度量的技術，但查詢的完整和準確程度仍有待提高。

本文結合時間序列分段集成近似表示（Piecewise Aggregate Approximation，PAA）方法[1，2]，提出了基于線性散列作為索引技術來處理時間序列查詢的新方法。在時間序列的預處理階段，提出一種新的規(guī)范化方法，很好的保留了時間序列的原始形態(tài)。采用線性散列索引機制，對時間序列進行有效靈活的存取，自然地處理存儲過程中產生的沖突。

在時間序列的查詢階段，提出了一種下界距離方法。并與K近鄰方法相結合，提高了查詢的效果，完成了用戶對于時間序列的查詢需求。

2 相關工作（Related work）

時間序列是隨著時間的先后順序而變化的多維的復雜數據類型。形式上時間序列表示為，其中元素是點的序列，，其中代表時間，代表時間序列在時刻的值。

國內外研究學者關于查詢處理的研究，大致可分成時間序列的表示方法、索引技術和相似性度量研究。

時間序列表示方法有離散小波變換（Discrete Wavelet Transform，DWT）[3，4]和離散傅立葉變換（Discrete Fourier Transform，DFT）[5]、奇異值分解法（Singular Value Decomposition，SVD）[6]、分段線性表示（Piecewise Linear Representation，PLR）[7，8]、符號化近似（Symbolic Approximation，SAX）[9，10]方法等。

時間序列索引技術分基于空間劃分的索引和基于數據劃分的索引，基于空間的劃分有K-D樹[11，12]、四叉樹[13]、網格文件[14]等，基于數據的劃分有R-tree[15]、iSAX-tree[16]和ADS-tree[17]。

時間序列的相似性度量是衡量時間序列相互之間聯系的方法。相似性度量是數據挖掘中的一項重要的任務。一般情況下，時間序列的每一種相似性度量方法都能夠對應一種或多種時間序列特征表示。例如，經典的時間序列PAA特征表示方法用到了歐式距離的度量方法，離散傅立葉變換通常會用到動態(tài)時間彎曲距離的度量方法。不同的特征表示選擇不同的度量方法，這要與設計的算法相結合。選擇一個適合的度量方法，可以提高算法的性能，提高時間序列查詢的查全率與查準率。經典的相似性度量方法主要有編輯距離、歐氏距離、動態(tài)時間彎曲距離等。為了進一步提高查詢效率，國外學者提出了下界距離的概念，下屆距離有LB-Yi距離和LB-Kim距離[18，19]等。

3 時間序列預處理（Preprocessing the time series）

3.1 時間序列規(guī)范化

給定某企業(yè)近幾年的原始交易值數據如圖1所示。

圖1中，橫坐標表示時間（天），縱坐標表示交易值（元）。從圖中可以看出，交易值數據分布相對不均勻，這就給后期建立索引，近似性匹配帶來了困難。所謂時間序列的規(guī)范化，就是在保留原來的總體趨勢的情況下，將原始的時間序列轉換至區(qū)間內。

這樣原始的時間序列就經過了規(guī)范化，與之前相比，規(guī)范后的時間序列，完美地保留了原始序列的趨勢，數據分布相對比較均勻。

3.2 時間序列分段

通常單條的時間序列規(guī)模也較大。如我國某地連續(xù)一年的氣溫數據。假設每小時檢測一次，那么連續(xù)一年有8760個數據點，索引全部點在時間和空間上代價都比較大。觀察天氣預報的規(guī)律可知，常常會報道某一天的平均氣溫，通常一天中溫度變化不大（個別地區(qū)除外）。就可以用平均氣溫來代表一天的氣溫，以24小時對時間序列分段，全年的氣溫時間序列就分成365段，直接索引這365段要比原始時間序列代價小很多。

定義一個時間序列，時間序列的集合組成了數據庫，假定Y的時間序列長度為n，將n單位的元素劃分成N段數。為了簡便，假定N是n的一個因數。

一條長度為n的時間序列X，通過向量表示為，要素通過以下公式計算得到。

假定只取一天當中的1點到16點的氣溫數據，組成了一條有16個元素的時間序列。選定分段數為4，這條時間序列被分成4個規(guī)整框。分別計算出每個規(guī)整框中數據的平均值。向量就成為時間序列分段之后的表示。這種轉換將原始時間序列轉換成了一個分段的常數近似。當N=n和N=1時轉換后的表示與原序列相同，分段如圖3所示。

3.3 時間序列離散化

大多數的時間序列都符合高斯分布，因而可采用離散化處理。高斯分布如表1所示。

給定一條標準的符合正態(tài)分布的時間序列，決定“斷點”使時間序列的目標變量分成若干個區(qū)域。表中a表示字母集的大小，即基。選擇字母集的大小，并且確定分裂點。將分段累計近似得到的序列的表示確定到所屬區(qū)間之后，用十進制進行編碼。選定字母集的大小a為4，對應斷點數為。從高斯分布表里可以看出，這三個斷點分別為（-0.67，0.00，0.67）。從圖4中可以看出，斷點數為3的區(qū)域劃分情況。劃分的區(qū)域分別用0、1、2、3表示。原始的時間序列X就會被離散化編碼為“0023”。

4 線性散列索引（Linear hash index）

4.1 線性散列索引概述

線性散列是一種動態(tài)的散列技術，基本思想是利用散列函數，將檢索的時間序列的值映射到固定的散列桶號，然后就可以找到待查的時間序列。

通過時間序列的規(guī)范化，使時間序列絕大部分都分布在標準正態(tài)分布的區(qū)間中，能解決數據分布的不均勻性。

線性散列輪轉分裂機制：定義一個循環(huán)級，在一個循環(huán)級內使用和這兩個散列函數。開始循環(huán)后，文件中的桶逐個分裂，一次循環(huán)分裂結束以后就開始下一輪的分裂，直至循環(huán)結束。有三種類型桶，已被分裂的桶、將要分裂的桶和分裂創(chuàng)建的映像桶。

線性散列索引在執(zhí)行插入操作時，在相應的桶編號對應的桶存滿的情況下就要觸發(fā)桶的分裂，在這之前增加一個溢出頁來存儲要插入的時間序列離散化后的表示。此時，要確定哪個編號的桶分裂，根據上文中的輪轉分裂機制確定，分裂的方式是依次分裂。即將要發(fā)生分裂的桶，也就是在第一個循環(huán)級，，的桶。要分裂的桶是以循環(huán)分裂的方式進行選擇，全部的桶都要進行分裂。

4.2 創(chuàng)建線性散列索引

假定散列表初始桶為，則值為時間序列的二進制離散化表示。時間序列二進制離散化表示時的最小位數用表示。

用表示當前循環(huán)級數，則每輪的桶數。第1輪，初始桶為。hash桶依次按編號分裂，用Next指示。

每次發(fā)生分裂的桶總由Next決定，為處理溢出情況，可以引入溢出頁來解決。線性散列索引文件初始創(chuàng)建的形態(tài)如圖5所示。

4.3 插入與刪除線性散列索引

線性散列索引在插入時，首先判斷時間序列符號化表示所對應的桶能否觸發(fā)分裂，如果條件成立，則發(fā)生分裂，產生映像桶和溢出頁。

插入h（r）=2321=100100010001，對應01編號，該桶未滿，不發(fā)生分裂，直接插入。插入h（r）=1330=10100110010，對應10編號，該桶已存滿，在插入“1330”時Next指向的00桶發(fā)生分裂，產生映像桶，映像桶的編號為Next+N0=4=100，同時，10桶產生溢出頁暫存“1330”，00桶里的數據在00桶和它的映像桶100桶之間進行重新分布。

插入h（r）=0211=11010011，取二進制的最后兩位11，對應11編號的桶，該桶未滿，不發(fā)生分裂，直接插入。插入h（r）=2031=11111101111，取二進制的最后兩位11，對應11編號的桶，該桶在繼插入“0211”之后已經存滿，所以在插入“2031”時Next指向的01桶就需要進行分裂，產生映像桶，映像桶的編號為Next+N0=5=101，同時，11桶產生溢出頁暫存“2031”，11桶和它的映像桶101桶之間進行數據重新分布，操作完成之后的數據分布如圖6所示。Next下移一位，Next=2。

5 時間序列的查詢 （Querying the time series）

5.1 近似查詢

數據挖掘應用需要近似查詢，線性散列索引能夠支持快速近似查詢，由于兩個相似的時間序列的符號化表示往往會相同，一次訪問就可實現。從線性散列索引文件中查詢所要結果的時間序列表示，順序掃描相應的時間序列作為近似查詢結果。

如給定時間序列，經過序列轉換后表示為“3102”，h（r）=3102=110000011110，取后兩位“10”位于Next=4和N=4之間，所以對應的桶已經發(fā)生分裂，此時取后三位“110”，定位相應110桶，查找到“3102”。返回查詢的結果BSF（Best-So-Far），它是一個粗略的結果集，叫做輸入實例時間序列的近似查詢。采用一種近似查詢和KNN（K-Nearest Neighbor）查詢組合的方式來縮小查詢空間，以提高查詢效率和查詢精度。

基于線性散列索引的精確查詢算法，將近似查詢得到的結果（BSF）作為輸入。因為BSF結果里的時間序列之間的距離相對較小，給最近鄰查詢創(chuàng)造條件，在近似查詢階段將大部分的搜索空間進行修剪，既提高了查詢精度，也降低了查詢時間。

K近鄰的核心在于找到實例時間序列的鄰居，也就是找到與目標序列相鄰的時間序列。衡量兩條時間序列是不是鄰居的判定標準，可直觀地理解為兩條時間序列之間的距離，如果距離在可接受的范圍，就可判定這兩條時間序列是鄰居。因為特征空間中兩條時間序列的距離能反映出兩條時間序列之間的相似程度。

K近鄰查詢將近似查詢得到的結果作為K近鄰中的數據集，當輸入新的時間序列時，在時間序列數據集中找到與目標時間序列最近鄰的K條鄰居，可認為這K條時間序列與目標時間序列最為相似。當K取1時，查詢到達了精確查詢。

輸入：BSF結果集，大小為，

其中，為時間序列的特征向量，目標時間序列特征向量。

輸出：目標時間序列特征向量的鄰居。

根據距離度量方法，在時間序列數據集（BSF結果集）S中找出與最臨近的K條時間序列，涵蓋這K條時間序列的的鄰域記做。相應的K近鄰法的模型對應的特征空間劃分如圖7所示。

假定特征空間所有的實例點組成了近似查詢結果集BSF，大小為。給定一個查詢實例時間序列X0，通過近似查詢得到X0粗略的結果集BSF，再從已有的BSF結果集中盡可能的剔除與X0不相近的時間序列，得到比較精確的結果集。兩條時間序列之間的距離表示它們之間的相似程度，有多種距離的計算方法，通常使用歐式距離、距離和Minkowski距離。假設Xi和Xj是特征空間里的兩條時間序列，它們之間的距離為：

5.2 緊密性討論

不直接取順序遍歷BSF結果集是因為時間耗費仍然比較大，用加入界限緊密性TLB（Tightness of Lower Bound）的方式來過濾掉一部分結果。所謂的TLB是一個對相似性度量非常有意義的方法，它的表達式如公式（5）所示。

其中，T和S是兩條時間序列。TLB的優(yōu)點是B實現了完全的自由測量，可對索引的有效性進行有效的預測。如果TLB的值為0，則證明這個索引需要從磁盤順序讀出時間序列，索引不具有高效性。如果TLB的值為1，則證明對索引稍微調整一下就可檢索出需要的一個時間序列，并且能夠保證得到真實的最近鄰。

給定時間序列T和S，長度都為n。假定T為查詢實例時間序列，S為待查序列，設置一個規(guī)整窗口R，恰好能把T分成w（w=1，2，…，w）塊，如圖11所示，當規(guī)整窗口R向指示的方向移動時T被分成了w塊區(qū)域，每個R就是一個區(qū)域，在每個區(qū)域里都會存在一個最大值，將每一塊的最大值，組成一條序列，取這條序列中最大值的均值，記作；最小值組成一條序列，取這條序列中最小值的均值，記作。它們的定義如公式（6）所示。

6 實驗評估（Experiments evaluation）

實驗環(huán)境：Intel（R） Core（TM） i3-4370 @ 3.8GHz，Windows 7操作系統(tǒng)，實驗程序采用Java語言編寫。

在進行離散化表示時選取的基數分別為[2，4，6，8，10]。

（1）選取不同的基數對下界緊密度（TLB）的影響。如圖9所示，固定時間序列長度為480時，基數對TLB的影響是非線性的，當基數變大時，TLB增長，并且增長速度越來越快，造成這種現象的原因是，在進行離散化表示時，選取的基數越大，相應的斷點數就越大，這樣時間序列離散越細化，離散化表示之后的時間序列越接近于原始時間序列，下界距離與真實歐式距離的比值就越接近于1。

（2）選取不同的時間序列長度對下界緊密度（TLB）的影響。如圖10所示，固定基數大小為10，之所以選取基數為10是因為從上圖中可以看出當基數是10的時候，TLB的值相比更接近于1，這樣實驗誤差更小一點，從圖中可以看出，當時間序列的長度增大的時候，下界緊密度越來越小。在設置的規(guī)整窗口大小不變的情況下，隨著時間序列的增大，規(guī)整窗口向右滑動時造成的誤差也是越來越大的，這勢必造成下界距離可靠性越來越差，TLB的值就會越來越小。

（3）選取不同的分段大小對時間序列表示耗時的影響。如圖11所示，固定時間序列的長度為480，隨著分段大小的不斷變大，系統(tǒng)耗時越來越小，當分段大小在40左右的時候，耗時在770ms處下降開始顯得不明顯，這主要是因為在分段之前有一步對時間序列進行規(guī)范化的過程，也可以理解成規(guī)范化一條長度為480的時間序列用時是770ms左右。

（4）選定時間序列長度為480，基數為10，分段大小選擇40。對系統(tǒng)的完整耗時進行測試，選擇對比實驗，結果如圖12所示。對比實驗主要分索引創(chuàng)建時間和查詢時間兩部分，其中索引創(chuàng)建時間是前期時間序列規(guī)范化表示，創(chuàng)建索引的時間總和表示。從圖12中可以看出，無論哪種方法，索引創(chuàng)建和預處理耗時占完整耗時中的大部分，而查詢時間占完整耗時中的小部分。在索引創(chuàng)建方面的性能提升與iSAX相比不明顯；主要是查詢方面的提升，從而驗證了下界距離的有效性。

7 結論（Conclusion）

本文基于已有的時間序列表示方法上，提出了關于時間序列規(guī)范化方法，并嘗試使用了線性散列創(chuàng)建時間序列的索引，在時間序列的相似性查詢方面提出了一種新的下界距離來衡量時間序列之間的相似度。經過實驗得出了時間序列規(guī)范化方法的有效性，驗證了線性散列在索引時間序列時，索引創(chuàng)建時間并沒有很大的提升，但是降低了時間序列查詢的時間。對提出的下界距離方法做了討論，效果比較理想。

參考文獻（References）

[1] Keogh E，et al.Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J].Knowledge & Information Systems，2001，3（3）：263-286.

[2] 劉芬，郭躬德.基于符號化聚合近似的時間序列相似性復合度量方法[J].計算機應用， 2013，33（01）：192-198.

[3] Chan K P，Fu W C.Efficient Time Series Matching by Wavelets[C].IEEE International Conference on Data Engineering.IEEE，1999：126-133.

[4] Zhou H A，Wang X M，Mei Y L.Theoretical Analysis of the Sound Absorption Characteristics of Periodically Stiffened Micro-perforated Plates[J].Acta Mechanica Sinica，2014，30（5）：714-726.

[5] Agrawal R，Faloutsos C，Swami A.Efficient Similarity Search in Sequence Databases[C].International Conference on Foundations of Data Organization and Algorithms.Springer-Verlag，1993：69-84.

[6] Korn F，Jagadish H V，Faloutsos C.Efficiently Supporting Ad Hoc Queries in Large Datasets of Time Sequences[J].Acm Sigmod Record，1999，26（2）：289-300.

[7] Pavlidis T，Horowitz S L.Segmentation of Plane Curves[J].IEEE Transactions on Computers，1974，C-23（8）：860-870.

[8] 喻高瞻，等.時間序列數據的分段線性表示[J].計算機應用與軟件，2007，24（12）：17-18.

[9] Lin J，et al.Experiencing SAX：A Novel Symbolic Representation of Time Series[J].Data Mining & Knowledge Discovery，2007，15（2）：107-144.

[10] 李桂玲，等.基于SAX的時間序列相似性度量方法[J].計算機應用研究，2012，29（3）：893-896.

[11] Ooi B C，McDonell K J，Sacks-Davis R.Spatialkd-tree：An Indexing Mechanism for Spatial Databases[C].IEEE COMPSAC，1987，87：85.

[12] 黃河，史忠植，鄭征.基于形狀特征k-d樹的多維時間序列相似搜索[J].軟件學報，2006，17（10）：2048-2056.

[13] Tayeb J，Ulusoy ，Wolfson O.A Quadtree-based Dynamic Attribute Indexing Method[J].The Computer Journal，1998，41（3）：185-200.

[14] Hinrichs K，Nievergelt J.The Grid File：A Data Structure Designed to Support Proximity Queries on Spatial Objects[R].Institut Fuer Informatik Zurich （SWITZERLAND），1983.

[15] Guttman A.R-trees：A Dynamic Index Structure for Spatial Searching[M].ACM，1984.

[16] Shieh J，Keogh E.I SAX：Indexing and Mining Terabyte Sized Time Series[C].ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM，2008：623-631.

[17] Zoumpatianos K，Idreos S，Palpanas T.Indexing for Interactive Exploration of Big Data Series[C].Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data.ACM，2014：1555-1566.

[18] Yi B K，Jagadish H V，Faloutsos C.Efficient Retrieval of Similar Time Sequences under Time Warping[C].Proceedings of the 14th International Conference on Data Engineering.IEEE，1998：201-208.

[19] Kim S W，Park S，Chu W W.An Index-based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases[C].Proceedings of the 17th International Conference on Data Engineering.IEEE，2001：607-614.

作者簡介：

戴 珂（1957-），男，本科，工程師.研究領域：軟件工程，

信息檢索.