李重文,鄧騰彬,馬世龍

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

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

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

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

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

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

1 概述

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

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

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

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

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

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

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

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

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

2 分段數(shù)據查詢顯示方法描述

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

2.1 基本定義

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

2.1.1 各時間段取點個數(shù)的確定

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

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

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

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

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

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

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

2.1.2 取點策略

取點策略包括如下部分:

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

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

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

2.1.3 分段個數(shù)的確定

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

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

2.2 具體過程

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

輸入 取點個數(shù)pcount,時間區(qū)間timeSE

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

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

3 實驗結果與分析

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

表1 實驗環(huán)境

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

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

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

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

(2)分別查出各段數(shù)據的起止時間點,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系統(tǒng)順序分配為從查詢返回的行的編號;1161043100000為實驗的查詢起始時間2006年10月17日07:58:20的長整數(shù)表示;1161935558000是查詢結束時間2006年10月27日15:52:38的長整數(shù)表示。

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

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

(5)開啟50個線程,每個線程負責處理一個時間段的曲線數(shù)據查詢及視圖更新。令50個時間分段中每個分段的起止時間分別為(t1,t2),(t3,t4),…,(ti,ti+1),…,(t50,t51),以及對應的時間段內要取點的個數(shù)為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為對應的表名稱;參數(shù)tvi=pavg/pi;tvi表示需要均勻間隔取點的間隔數(shù);ti,ti+1分別表示第i個時間段的起始和結束時間值。

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

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

圖3 全部數(shù)據點查詢曲線繪制截圖

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

4 結束語

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

[1] 李重文,李先軍,葉 鋼,等.一種大數(shù)據量的曲線顯示查詢方法:中國,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] 覃 征,李愛國.時間序列數(shù)據的穩(wěn)健最優(yōu)分割[J].西安交通大學學報,2003,37(4):338-342.

[5] 肖 輝,胡運發(fā).基于分段時間彎曲距離的時間序列挖掘[J].計算機研究與發(fā)展,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);湖南師范大學青年優(yōu)秀人才培養(yǎng)計劃基金資助項目(ET13108);東莞市高等院校科研機構科技計劃基金資助項目(20121081001019)。

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

2013-10-10

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