基于分段極值的時間序列數據查詢顯示方法

李重文,鄧騰彬,馬世龍

(1.湖南師范大學工程與設計學院,長沙410081;2.東莞電子科技大學電子信息工程研究院,廣東東莞523808; 3.北京航空航天大學軟件開發環境國家重點實驗室,北京100191)

基于分段極值的時間序列數據查詢顯示方法

李重文1,鄧騰彬2,馬世龍3

(1.湖南師范大學工程與設計學院,長沙410081;2.東莞電子科技大學電子信息工程研究院,廣東東莞523808; 3.北京航空航天大學軟件開發環境國家重點實驗室,北京100191)

時間序列數據在許多領域廣泛存在,有海量和復雜的特點,直接查詢出所有的原始數據并對其進行分析十分耗時,且對計算機的內存消耗極大。為此,提出一種基于分段極值的時間序列數據查詢顯示方法,對需要查詢分析數據的時間范圍進行分段,根據各個時間段數據的極值及總取點個數來確定該時間段的取點個數,通過數據庫本身的查詢機制實現均勻取點,并結合多線程機制實現各時間段數據的并行查詢及曲線繪制。實驗結果表明,與傳統查詢及可視化方法相比,該方法能夠指定取點數量,并在取點數量確定的情況下,繪制曲線能較好地逼近原始曲線,且極大地縮短曲線的查詢繪制時間,具有較好的工程實用性。

時間序列;數據庫查詢;時間序列數據庫;曲線繪制;數據壓縮;數據分析

1 概述

時間序列數據在醫學、金融、傳感器網絡、移動對象、自動化測試[1]等領域廣泛存在,并且在生物序列分析、金融數據分析、傳感器網絡監控等領域成功應用。

當前關于時間序列數據的研究主要集中在相似性搜索[2-3]、時間序列分割與模式發現[4-5]及時間序列的預測[6-7]等,并取得了大量的研究成果。時間序列可視化也是一個應用前景廣闊的研究方向[8-11],國外研究較多,并開發出了相應的可視化工具,如 time-series on spirals[12],time searcher[13], vizTree[14],time-series bitmaps[15]等,但這些工具主要還是集中在對時間序列數據模式發現的可視化、模式展現形式的多樣性等方面的研究。對于某些領域,如航天器測試中對數據分析的重點并非模式發現或者時間序列預測,而需要直接對原始數據進行查詢分析,由測試人員來對數據的正確性進行判斷,因此,目前已有的可視化工具都無法滿足該需求。

當時間序列數據存儲于時間序列數據庫后,為便于分析,比較常用的方法是從數據庫中檢索數據,并將數據以曲線的形式展現出來,使得數據分析人員能夠直觀地對檢索的數據趨勢以及局部數據進行分析。但是由于數據的時間密度大,如在航天器測試應用中按照1 s 1條記錄計算,一天的數據量就是86 400條,按照1周為數據分析周期,則總的數據量為604 800條。將如此多的數據一次全部檢索出來并繪制出曲線是不大可行的:一方面將數據從數據庫中檢索出來需要耗費大量的時間,漫長的響應等待時間是用戶難以接受的;另一方面巨大的數據量會消耗分析軟件大量的內存空間,當數據量再變大,實現數據的全部繪制就不可行了。

傳統的解決方案都是將大量的數據以分頁的形式進行處理,即每次檢索出固定數量的數據并繪制出曲線,當用戶點擊下一頁時再將相同數量后一個時間段的數據檢索出來進行繪制。這樣做有如下不足:假設每頁數據顯示2 000條時,這些數據按照1 s 1條計算,僅涉及了約33 min的數據,對于1周的分析周期顯得過于短暫,分析人員無法對1周數據的大致發展趨勢進行判斷,同時也無法快速定位異常數據所處的時間區間。

另一個解決思路是采用常見的曲線壓縮算法如Douglas-Poiker法、線段過濾法、垂距限值法等對數據進行壓縮,從而進行曲線繪制。這些算法的優點是都能取出較能體現曲線特征的特征點,從而使繪制出的特征點曲線能較好地逼近原始曲線。但是,將這些算法應用在這種極大數據量的環境中存在2個問題:

(1)這些算法都需要遍歷所有的數據,并進行數據之間的運算才能取出特征點。如果按照前面所述的1 s 1條數據,從數據庫中查詢出一周的數據而不進行任何數據之間的運算都需要較長時間,再加上數據運算,繪制曲線需要的時間顯然是不可接受的。

(2)這些算法雖然都能壓縮數據量,但是壓縮程度都依賴于某個閾值,如Douglas-Poiker法和垂距限值法都需要指定某個垂距作為數據過濾的閾值,線段過濾法需要指定線段長度作為數據過濾的閾值。對于不同的數據需要不同的閾值,分析人員往往無法直接提供出合適的閾值。

目前,針對這種大數據量數據的一次曲線顯示查詢還沒有較好的解決方案。

本文提出基于分段極值的時間序列數據查詢顯示方法,該方法可以指定取點的總個數,并根據較少的數據點體現數據的變化趨勢,結合多線程機制提高響應速度。

2 分段數據查詢顯示方法描述

本文方法的基本思路為:對整個需要查詢分析的時間區間進行分段,每個分段按照一定的策略分別獲取不同個數的數據點,以各個分段獲取的數據點集合作為整個時間區間的趨勢變化點集;另外,為加快整個曲線的查詢繪制響應速度,每個分段時間區間分別開啟單獨線程來進行數據的查詢分析及更新曲線視圖。

2.1 基本定義

假設需要取點的總個數為pcount,該數據可由用戶設定或程序根據用戶顯示器屏幕分辨率自動確定。整個時間區域分成n個時間段。

2.1.1 各時間段取點個數的確定

按照一般統計規律,對于任意2個跨度相同的時間段,極值相差較大的時間段能夠容納更多的數據變化信息,即隱藏著更多曲線變化,因此宜采集較多的數據點;而對于極值相差較小的時間段,說明該時間范圍內數據變化平緩,則可選取少量數據點。因此,將較多的點取自變化較大的時間段,較少的點取自變化平緩的時間段,能夠在總的取點個數一定的情況下較好地反映總的數據變化情況。

為了描述數據變化程度,對于第i個時間段值的變化情況,本文使用值的絕對距離di來衡量,即:

其中,maxi為第i個時間段內數據的最大值;mini為第i個時間段內數據的最小值。

根據式(1),所有分段的絕對距離之和為:

根據每一個時間段的絕對距離di在總的絕對距離之和sum所占的比例來確定第i個分段的取點個數,即:

對于式(3),pi的確定適合于di不等于0的情況,當di等于0時,說明該時間段值無變化,則取pi=2,因此綜合2種情況,pi的取值為:

其中,i的取值范圍為0＜i≤n。pi在根據式(3)計算時,結果按照四舍五入取整數。

2.1.2 取點策略

取點策略包括如下部分:

(1)當di=0時,pi=2,說明第i時間段內的數據無變化,因此,選取第i個時間區間的首尾2個點即可代表該時間段的曲線特征。

(2)為加快數據查詢及曲線繪制響應速度,避免Douglas-Poiker等方法須將所有數據都查詢出來并進行計算及其耗時的缺陷,本文采用均勻取點的策略,即從所有數據點中按照點的序號等間隔地取點。均勻取點一方面能夠根據總數據量和均勻間隔有效控制取點個數;另一方面均勻取點能夠直接得到數據庫的支持,主流大型數據庫如ORACLE,DB2等通過SQL語句就能實現均勻取點,數據庫查詢出的點即目標點,能夠極大地縮短查詢取點耗時。

(3)對于每個時間段,最大值及最小值也作為目標點進行查詢及曲線繪制。

2.1.3 分段個數的確定

令整個需要進行查詢分析時間區域的數據總個數為total,在取點數量pcount確定的情況下,顯然分段越多取出的數據點越能體現原始數據的變化趨勢,因此可取:

但是由于n越大,開啟的并行處理線程越多,也將消耗更多的系統資源,因此根據經驗n的取值一般不超過50。

2.2 具體過程

曲線查詢繪制子過程drawTendencyCurve如下:

輸入 取點個數pcount,時間區間timeSE

輸出 由取點集合繪制的曲線

在主過程中,如果用戶要進一步查看某段時間區間的數據,則在已繪制的曲線顯示視圖上通過鼠標選定某個區間,將該區間的橫坐標時間范圍作為新的查詢時間區間,然后再次調用上述子過程進行曲線查詢繪制,使數據分析人員可進一步查看所選時間區域數據的細節,如果用戶不需要進一步查看數據,則結束本次曲線繪制。

3 實驗結果與分析

現有一個航天領域內測試數據管理的應用系統。該應用系統提供的主要功能包括對海量的航天器試驗數據進行數據入庫以及數據查詢分析。該應用系統的數據庫中主要數據表的字段分別為時間、[參數1]、[參數2]、[參數3]、……,其中時間作為主鍵,精確到ms,時間列在數據庫中存儲的數據類型為長整型數據。數據庫系統采用ORACLE 9I數據庫。該應用系統的數據查詢分析子系統基于本文方法對測試數據進行查詢以及曲線繪制,子系統采用 Java語言實現,曲線繪制使用的是開源JFREECHART工具包,運行于普通PC。實驗環境如表1所示。

表1 實驗環境

數據庫中存儲有一年的航天器測試數據。實驗過程為按本文方法取3 000個點進行曲線繪制,然后取出該時間段所有數據點進行曲線繪制,比較兩者的耗時及曲線形態。

本次實驗查詢的參數為A01,查詢時間范圍為2006年10月17日-10月27日共10天的數據,數據量為405 300條,曲線視圖中橫坐標表示時間,縱坐標表示參數編號為A01中的數值。

下文詳細分析實驗中數據的查詢及曲線繪制過程:

(1)根據式(5)得出的n值均遠大于50,故此處n取值為50,即分成50個時間段,每個時間段所含的數據量為pavg=405 300/50=8 106條。

(2)分別查出各段數據的起止時間點,SQL語句為:SELECT time FROM(SELECT time,ROWNUM from tb_name WHERE time BETWEEN 1161043100000 AND 1161935558000 AND(A01 IS NOT NULL)) WHERE MOD(ROWNUM-1,pavg)=0,其中,tb_name為對應表的名稱;ROWNUM是ORACLE系統順序分配為從查詢返回的行的編號;1161043100000為實驗的查詢起始時間2006年10月17日07:58:20的長整數表示;1161935558000是查詢結束時間2006年10月27日15:52:38的長整數表示。

(4)初始化曲線繪制視圖,將所有已獲取各時間段的最大值與最小值繪制于曲線顯示視圖中。本次實驗中50個時間分段的最大值與最小值一共為100個數據點,采用連線的形式將100個點在曲線顯示視圖中顯示出來,如圖1所示。

圖1 最大最小值曲線繪制截圖

(5)開啟50個線程,每個線程負責處理一個時間段的曲線數據查詢及視圖更新。令50個時間分段中每個分段的起止時間分別為(t1,t2),(t3,t4),…,(ti,ti+1),…,(t50,t51),以及對應的時間段內要取點的個數為pi,則第i個線程構造的SQL查詢語句為:SELECT time, A01 FROM(SELECT time,A01,ROWNUM FROM tb_ name WHERE time BETWEEN tiAND ti+1AND A01 IS NOT NULL)WHERE MOD(ROWNUM-1,tvi)=0,其中,tb_name為對應的表名稱;參數tvi=pavg/pi;tvi表示需要均勻間隔取點的間隔數;ti,ti+1分別表示第i個時間段的起始和結束時間值。

(6)當50個線程都處理完成時,則曲線繪制完畢。用戶可以查看所繪制的曲線,分析曲線整體的趨勢,以及其是否存在異常,并將所繪制的曲線數據保存起來供后續查看分析。

本次實驗曲線繪制完畢后在曲線顯示視圖中的顯示如圖 2所示,繪制的數據點個數一共為3 010個,由于pi的計算采用了四舍五入,且tvi的計算也是取整,因此總的取點個數只會近似于pcount。對比圖3未使用本文方法將所有數據進行繪制的顯示圖,可以看出兩者的曲線相當逼近,圖2以較少的數據點很好地體現了圖3的曲線特征,并且采用本文方法最終的耗時僅為5 s,遠小于取出全部數據的572 s耗時,當采用Douglas-Poiker法或者垂距限值法時,因為還存在數據運算,顯然時間會大于572 s。

圖3 全部數據點查詢曲線繪制截圖

通過實驗可以看出,本文方法無論在時間、空間上都優于其他曲線壓縮算法,并且具有較好的曲線特征提取效果,能夠更好地應用于工程實踐中。在航天器測試領域,大部分參數的變化都應該遵循某個變化規律或者變化的幅度處于某個指定的區間,數據分析人員通過繪制的曲線能很容易找到這些特征,并定位異常數據。本文方法對分析該航天器是否存在異常提供了便利,方便數據分析人員在短時間內查看長時間數據的曲線走勢,根據該曲線判斷是否存在異常,并且能夠快速定位異常數據的位置,根據定位到的異常數據進一步分析該航天器的哪個部分出現問題。

4 結束語

時間序列數據由于其龐大的數據量,傳統的數據查詢及可視化方法在時空效率上都難以取得理想效果。本文結合航天器測試領域內的數據分析需求,提出一種基于分段極值的時間序列數據查詢顯示方法。通過對要查詢分析的時間范圍進行分段,在各分段內部采用均勻取點,由于數據庫本身支持均勻取點,因此能夠獲得較快的取點速度,實驗結果表明,該方法在時空效率及查詢效果上具有較好的工程實用性。目前,本文方法已經成功應用于多個型號的航天器測試數據分析系統中。如何更為合理地確定各分段取點個數將是下一步將要解決的問題。

[1] 李重文,李先軍,葉 鋼,等.一種大數據量的曲線顯示查詢方法:中國,ZL 201010555587.4[P].2011-12-07.

[2] Yang Yin,Papadopoulos S,Papadias D,et al.Authenticated Indexing for Outsourced Spatial Databases[J]. VLDB Journal,18(3):631-648.

[3] Bueno R,Traina A J M,Traina J C.Genetic Alogorithms for Approximate Similarity Queries[J].Dataand Knowledge Engineering,2007,62(3):459-482.

[4] 覃 征,李愛國.時間序列數據的穩健最優分割[J].西安交通大學學報,2003,37(4):338-342.

[5] 肖 輝,胡運發.基于分段時間彎曲距離的時間序列挖掘[J].計算機研究與發展,2005,42(1):72-78.

[6] 薛海東,朱群雄.基于結構化類比的時間序列預測算法[J].計算機工程,2010,36(1):211-214.

[7] 劉志剛,杜 娟,許少華,等.基于過程神經元網絡的時間序列預測方法[J].計算機工程,2012,38(5): 199-201.

[8] Yu Jin,Hunter J,Reiter E,et al.Recognising Visual Patterns to Communicate Gas Turbine Time-series Data [C]//Proc.of the 22nd SGAI International Conference on Knowledge Based Systems and Applied Artificial Intelligence.London,UK:Springer,2002:105-118.

[9] Hochheiser H,Shneiderman B.VisualQueries for Finding Patterns in Time Series Data[D].Baltimore, USA:University of Maryland,2002.

[10] Hochheiser H,Shneiderman B.Visual Specification of Queries for Finding Patterns in Time-series Data[D]. Baltimore,USA:University of Maryland,2001.

[11] Hochheiser H.Interactive Graphical Querying of Time Series and Linear Sequence Data Sets[D].Baltimore, USA:University of Maryland,2003.

[12] Weber M,Alexa M,Muller W.Visualizing Time-series on Spirals[C]//Proc.of IEEE Symposium on Information Visualization.San Diego,USA:IEEE Press, 2001:7-13.

[13] Hochheiser H,Shneiderman B.Dynamic Query Tools for Time Series Data Sets:Timebox Widgets for Interactive Exploration[J].Information Visualization,2004,3(1): 1-18.

[14] Lin J,Keogh E,Lonardi S.Visualizing and Discovering Non-trivial Patterns in Large Time Series Databases[J]. Information Visualization,2005,4(2):61-82.

[15] Kumar N,Lolla N,Keogh E.Time-series Bitmaps:A Practical Visualization Tool for Working with Large Time Series Databases[C]//Proc.of SSIAM'05. Newport Beach,USA:[s.n.],2005:531-535.

編輯 任吉慧

Method for Query and Display of Time-series Data Based on Extreme Value of Segmented Periods

LI Zhong-wen1,DENG Teng-bin2,MA Shi-long3
(1.College of Engineering&Design,Hunan Normal University,Changsha 410081,China;
2.Institute of Electronic and Information Engineering in Dongguan,University of Electronic Science and Technology of China, Dongguan 523808,China;3.State Key Laboratory of Software Development Environment,Beihang University,Beijing 100191,China)

Time-series is a kind of important data object and is ubiquitous in the world.Due to its very large quality and complexity,data query and analysis base on the source data do pay high costs on time and memory of computer.A method for querying and displaying time-series data based on segmented extreme value is proposed.It segments the range of time to be queried and analyzed into periods of time,and then determines the number of access points in a period of time according to extreme value of each period of time and the total number of access points,accessing the points uniformly through a database query mechanism itself and combined with multi-threading mechanism to achieve parallel query and curve drawing of each time period data.Experimental results show that compared with traditional methods,the number of access points is able to be specified,and the drawn curve has a good approximation of the original curve in the case that the number of access points are determined.It is able to greatly shorten the curve querying and drawing time,

with good engineering practicality.

time-series;database query;time-series database;curve drawing;data compression;data analysis

1000-3428(2014)09-0027-05

A

TP311.13

10.3969/j.issn.1000-3428.2014.09.006

湖南省自然科學基金資助項目(13JJ6029);湖南師范大學青年優秀人才培養計劃基金資助項目(ET13108);東莞市高等院校科研機構科技計劃基金資助項目(20121081001019)。

李重文(1981-),男,博士,主研方向:海量數據處理,自動化測試;鄧騰彬,助理研究員;馬世龍,教授。

2013-10-10

2013-12-19E-mail:lee_zw@163.com