基于動態(tài)變粒度的改進基態(tài)修正模型研究

姚茂華　周文婷

[摘要]分析基態(tài)修正模型的特點和研究進展,提出基于動態(tài)變粒度的改進基態(tài)修正模型,該模型引入動態(tài)變粒度基態(tài)距因子來確定基態(tài)距閥值,是對基態(tài)修正模型進行進一步改進,提高歷史數據的存儲和檢索效率;針對該改進基態(tài)修正模型,分析時空數據的檢索方式,實現多種方案的時空數據檢索。

[關鍵詞]時態(tài)GIS 時空數據模型 基態(tài)修正 時空數據檢索

中圖分類號:TP3文獻標識碼:A文章編號:1671-7597(2009)0910043-03

一、引言

由于時間是反映地理實體的狀態(tài)和演變過程的重要組成部分,任何地理實體都有其產生、發(fā)展和滅亡的時間過程,因此,在描述地理實體的空間和屬性特征的同時,也必須描述它具體的存在時間,才能反映客觀真實世界。能夠處理時間信息的時態(tài)地理信息系統(Temporal Geogaphical Information System,簡稱TGIS)就成為GIS研究的熱點。

TGIS的關鍵問題是建立合適的時空數據模型,許多學者提出了多種時空數據模型來存儲時態(tài)數據,主要包括:序列快照模型、基態(tài)修正模型、時空復合模型、第一范式時空數據模型、非第一范式時空數據模型、基于事件的時空數據模型等。其中,基態(tài)修正模型不存儲研究區(qū)域內的每個時刻的全部信息,只存儲某個時刻的全部信息(基態(tài))以及其他時刻相對于基態(tài)時刻的信息變化量,得到了越來越廣泛的關注[1]。

二、基態(tài)修正模型特點

基態(tài)修正模型是Peuquek和Duan于1995年提出的[2]?；鶓B(tài)修正模型按事先設定的時間間隔采樣,只儲存某個時刻的數據狀態(tài)(稱基態(tài))和相對于基態(tài)的變化量。由于對于每一次變化,基態(tài)修正模型僅記錄變化的增量,只有很小的數據量需記錄,因此數據冗余較少,而且也能充分地表達地物的變化情況。然而,在對某一歷史時刻查詢的時候需要按順序進行數據疊加操作,整合出一套完整的空間數據,當時間比較久遠、變化次數較多時,對歷史數據的檢索時間較長,查詢的效率會非常低。如何減少數據冗余、高效地進行查詢和分析,已經成為許多學者研究的問題[3-5]。

三、基態(tài)修正模型的改進方法

針對傳統的基態(tài)修正模型對歷史數據的檢索時間長的問題,研究基態(tài)修正模型的學者對于傳統的基態(tài)修正模型進行改進和擴展主要圍繞如何更科學的設置基態(tài)和快速索引展開。張祖勛等(1996)提出了建立多級差文件的方法減少歷史數據恢復時檢索差文件的個數[6];曹志月(2002)等人認為當歷史久遠時建立多級差文件方法仍不理想,提出了多基態(tài)修正法,提高檢索的速度[7];劉仁義等(2002)認為時態(tài)數據庫用戶對數據具有厚今薄古或對某一特定時期操作頻繁的特點,提出了雙基態(tài)/多基態(tài)修正,并在理論探討的基礎上,進一步采用區(qū)段快速索引和變粒度存儲技術提高了時態(tài)查詢效率[8];余志文等(2003)提出了面向對象方法的基態(tài)修正模型以及基態(tài)距因子與等比系數方法等;張保鋼(2005)認為當歷史久遠時,基態(tài)的占用空間仍是非常可觀的,提出了多基態(tài)多級差文件修正方法[9];李勇(2005)以對象變化臨界指數確定基態(tài)距的方法[10],改進基態(tài)修正時空數據模型?，F在修正模型的理論與技術兩方面發(fā)展相對較為成熟,且已在土地、房產等相關領域的TGIS系統中得到應用。

總結基態(tài)修正時空數據模型的存儲方式及其改進方法,主要有以下幾種比較典型的基態(tài)修正方式[11]。

圖1(a)是Langran[12]的基態(tài)修正方式,只記錄了一個數據基態(tài)和相對于基態(tài)的變化值,這種方式在發(fā)生變化的對象數量很多時,由于關系表中存儲了太多的歷史數據,因而對歷史數據進行檢索時速度很慢,查詢效率很低。

圖1(b)是張祖勛等[6]改進后的基態(tài)修正方式。他們把時間段T分成兩部分,對前半段時間,從起始狀態(tài)不斷閱讀差文件,狀態(tài)不斷沿著時間軸正向變化,直到查詢到所需時刻為止;而對后半段時間,從現在狀態(tài)不斷閱讀差文件,狀態(tài)不斷沿著時間軸反向變化,直到查詢到所需時刻為止。這種方式同樣有其不足之處:將時間段T分成兩部分只是臨時性地解決檢索時歷史數據過多的問題,當時間段T進一步延長時(比如當T延長到2倍時),此方法實際上就沒有任何意義了。

圖1(c)是曹志月等人提出動態(tài)多級索引方法[7],在整個歷史狀態(tài)中動態(tài)地設立多個基態(tài),基態(tài)間的差文件數,稱為基態(tài)距(k)。系統中,隨著對象歷史狀態(tài)的插入、修正,以及對歷史時期的檢索頻繁程度而動態(tài)地創(chuàng)立基態(tài)。當用戶對某時間段的檢索較頻繁時,特別是對于連續(xù)變化的時空過程,差文件的恢復中大量的連續(xù)變化屬性的推導過程會占去較大的時間開銷,通過動態(tài)創(chuàng)建差文件和基態(tài)的方法,緩解了這一問題,動態(tài)多級索引方法大大提高了查詢效率。但是,基態(tài)距k是等距的,基態(tài)的分布位置不是最優(yōu)的基態(tài)位置。

圖1(d)和圖1(e)是張寶鋼等在曹志月等人提出的動態(tài)多級索引方法的基礎上增加單級和多級時間索引,提出的多基態(tài)多級差文件修正方法[9],該方法中,基態(tài)仍以快照方式存儲,基態(tài)數沒有增加,每兩個基態(tài)之間增加了3個的差文件,數據的存儲空間基本沒有增加,數據檢索的速度卻有很大的提高。然而,當基態(tài)距較小時或是歷史較久遠時,基態(tài)個數會隨之增加,也就意味著較大的數據冗余。

圖1(f)是余志文等[11]根據變粒度基態(tài)距因子理論提出修正方式。其基本思想是:各個歷史時期查詢的頻繁程度是不同的,離現在時刻越遠的歷史時期,查詢的頻繁程度越小;離現在時刻越近的歷史時期,查詢的頻繁程度越大。因此,引入變粒度基態(tài)距因子,離現在時刻越遠的基態(tài)之間的基態(tài)距越大,離現在時刻越近的基態(tài)之間的基態(tài)距越小。但是,對于在短時間內數據變化頻繁的情況下,基態(tài)距與時間的相關性會減弱。

圖1(g)是李勇[10]提出根據“對象變化臨界指數(M)”來確定基態(tài)距的基態(tài)修正方式。其基本思路為:①造成數據檢索時間長的根本原因是數據量。②事物的變化都是一個從“量變到質變”的過程,而在這個過程中,總會有一個臨界點,當達到或超過這個臨界點時,就會發(fā)生質變。因此,兩個相鄰基態(tài)之間的基態(tài)距既不是等距的,也不是隨時間的迫近而遞減的,而是根據對象發(fā)生變化是否達到或超過對象變化臨界指數(M)來確定的。這里的關鍵問題是M值如何確定,其中,相鄰兩個基態(tài)的前一個基態(tài)的數據量是決定因子之一,還有就是相鄰兩個基態(tài)之間對象發(fā)生變化的次數,發(fā)生變化的次數越多,數據庫中增加的記錄就越多。但是,影響M取值的因子很多,確定比較困難。

四、動態(tài)變粒度的改進基態(tài)修正模型

基態(tài)修正模型減少數據冗余的秘訣在于在對象發(fā)生變更時,只存儲該時刻的變化量(差文件),而不存儲該時刻所有數據以避免重復存儲,但是隨著變化的頻度和力度的加大,會增加差文件的數量,因此進行歷史回顧時,必須依賴該時刻與當前時刻間的各個差文件和當前基態(tài)進行逐步回退求解,這個計算量隨著時間的推移和變化的加快會成倍增長。為了使歷史回溯檢索的時間縮短,需要建立新的基態(tài),作為此段時間的檢索起點,縮短對較遠的歷史數據的查詢時間,其中一個關鍵的問題是基態(tài)距閥值的確定。有些改進的基態(tài)修正模型隨時間的發(fā)展不斷增加基態(tài)的占用空間,降低檢索時間的開銷,因此,基態(tài)距閥值的確定需要對這兩方面進行權衡,閥值太小會浪費空間,閥值太大又會占用過多時間。如果根據數據變化數量和查詢頻率確定基態(tài)距閥值,適當地在對象發(fā)生變化的過程中記錄若干個基態(tài),則不會造成太多的數據冗余,并可提高歷史回顧的效率。

動態(tài)變粒度的改進基態(tài)修正模型就是基于上述思想設計的時空數據存儲模型(如圖2所示)。對象發(fā)生變化,就會有相應于上一次變化的差文件產生,基態(tài)距是兩個基態(tài)間的差文件數,兩個相鄰基態(tài)之間的基態(tài)距不是等距的,需要動態(tài)變化,動態(tài)地建立基態(tài),只有與查詢頻率分布和變化數量分布相符合的基態(tài)分布位置才是最好的基態(tài)位置。各個歷史時期查詢的頻繁程度是不同的,離現在時刻越遠的歷史時期,查詢的頻繁程度越小;離現在時刻越近的歷史時期,查詢的頻繁程度越大。不同時間段的數據變化更新數量直接影響差文件數,變化次數越多,差文件越多,查詢的等待時間越長,反之則越短。因此,影響基態(tài)距的因子有:數據變化數量和離現在時刻的遠近。

因此,引入動態(tài)變粒度基態(tài)距因子,數據變化更新數量和離現在時刻的遠近決定基態(tài)距閥值。除了起始基態(tài)外,其余的基態(tài)都要隨著時間的不斷前移而每隔一段時間進行自動更新?；鶓B(tài)距是根據對象發(fā)生變化是否達到變化閥值Q確定的。

在分析影響基態(tài)距的因子后,引入系數a(a≠1),設ti時刻距現在時刻的時間差為△ti,在△ti時間內的差文件數為qi,基態(tài)距閥值為Qi,則Qi=a×△ti。當在△ti時間內,變化差文件數qi大于或等于基態(tài)距閥值Qi時(即qi≥Qi),需要產生基態(tài),如圖2所示。時間差△ti越小,基態(tài)距閥值Qi越小;時間差△ti越大,變化基態(tài)距閥值Qi越大。設起始狀態(tài)距現在時刻的時間差為△t0,變化差文件數為q0,即為總差文件數,也是基態(tài)距閥值Q0(Q0=q0),由Q0=a×△t0,則可確定系數a。

當△ti較小時,即離現在時刻很近時,若變化差文件數qi小于基態(tài)距閥值Qi,則在該時刻不設立基態(tài);當△ti較大時,即離現在時刻很遠時,若變化差文件數qi小于基態(tài)距閥值Qi,則在該時刻也不設立基態(tài)。

隨著時間的推移,基態(tài)距閥值逐漸變大,通過上述公式,可以求出新基態(tài)所在的差文件位置,舊基態(tài)加上新舊基態(tài)時間段內的差文件,即可更新為新基態(tài)。

動態(tài)變粒度的改進基態(tài)修正模型在整個時間過程中,隨著時間的推進和對象的變化,考慮了數據的變化數量和數據的查詢頻率對數據查詢效率的影響,根據對象變化是否達到變化閥值Qi,動態(tài)地創(chuàng)建基態(tài),使得對對象信息進行恢復時,可以緩解大量的差文件疊加而占用的時間開銷,提高查詢效率。

五、時空檢索

時空數據的檢索包含兩個方面的條件:時間條件和空間條件。本文主要關注時態(tài)問題(時間條件)。

基于基態(tài)修正的時空數據檢索主要有兩種方式:一種是基于時間點的檢索,另一種是基于時間段的檢索(即查詢兩個事件時間之間的數據)[13]。時間點檢索方式的實現較為簡單,當用戶輸入檢索的時間(tj)時,首先判斷與所要查找時間點之間差文件數最少的基態(tài)(基態(tài)n),然后在該基態(tài)的基礎上疊加差文件,就可以得到用戶所要的結果,如圖3所示。

時間段的檢索方式要復雜一些,根據兩個事件時間所處的區(qū)域不同,分為如下的4種情況,如圖4所示。

圖4(a)中tj=tk,這種情況實際上就是基于時間點的檢索。

圖4(b)中tj與tk處于相鄰的兩個基態(tài)之間,兩個事件時間之間沒有基態(tài)的存在。這時首先計算tj時刻和tk時刻與基態(tài)n-1和基態(tài)n之間差文件數最少的基態(tài),若tj->tn-1的差文件數小于tk->tn的差文件數,則加載基態(tài)n-1,然后在此基礎上加上tn-1->tj的差文件,就得到tj時刻的快照,tj->tk時間段產生的對象就可以從tj時刻的快照到tk時刻的差文件獲得;若tj->tn-1的差文件數大于tk->tn的差文件數,則加載基態(tài)n,然后在此基礎上加上tn->tk的差文件,就得到tk時刻的快照,tj->tk時間段產生的對象就可以從tk時刻的快照到tj時刻的差文件獲得。

圖4(c)中tj與tk之間有一個基態(tài)n的存在。這時可以首先計算出tj->tn的差文件,然后再加上tn->tk的差文件,兩個差文件的和就是tj與tk之間產生的對象。

圖4(d)中tj與tk之間有多于1個基態(tài)的存在。首先計算出tj->tn-1的差文件,然后再計算出tn->tk的差文件。tn-1->tn的差文件只需要計算出基態(tài)n-1與基態(tài)n之間的變化情況,于是就可以得到tj->tk的差文件。

根據上面的分析,可以得到兩個事件時間tj與tk之間的時空對象的查詢方法,其流程如圖5所示。

六、結論

運用動態(tài)變粒度基態(tài)距因子確定基態(tài)距閥值的方法,考慮了基態(tài)距與數據變化數量和時間查詢頻繁程度相關的問題,系數a的引入實現了基態(tài)動態(tài)更新,更好地優(yōu)化了歷史數據的存儲和檢索效率問題,并具備較強的實用性和靈活性。同時,針對時空數據查詢分析,實現了基于時間點和時間段的不同方式的數據檢索,提高了歷史數據的檢索效率。

基于動態(tài)變粒度的改進基態(tài)修正模型解決了數據的存儲和檢索問題,但對時空數據的空間關系問題并沒有解決。因此,需要對基態(tài)修正模型進行進一步的擴展研究,解決對時空對象空間關系處理和時空數據的組織問題。

參考文獻:

[1]劉睿、周曉光,一種基于動態(tài)基態(tài)方法的時空數據模型擴展[J].測繪通報,2008,6:50～53.

[2]Peuquet D J,Duan N.An Event-Based Spatio-Temporal Data Model(ESTDM) for Temporal Analysis of Geographical Data[J].International Journal of Geographical Information System,1995,9(1):7～24.

[3]PEUQUET D J DUAN N.An Event-based Spatio-temporal Data Model(ESTDM) forTemporal Analysis of Geographical Data[J].Intemational Journal of Geographical lnformation Systen,1995,9(1):7-24.

[4]LANGRAN G,CHRISMAN R.A Framework forTemporal Geographic lnformation[J].Cartographica1988.25(3):11-14.

[5]張祖勛、黃明智,時態(tài)GIS數據結構的探討[J].測繪通報,1996(1):19-22.

[6]張祖勛、黃明智,TGIS數據結構的研討[J].測繪通報,1996,(1):19～22.

[7]曹志月、劉岳,一種面向對象的時空數據模型[J].測繪學報,2002,31(1):87～92.

[8]劉仁義、劉南,基態(tài)修正時空數據模型的擴展及在土地產權產籍系統中的實現[J].測繪學報,2001,30(2):168～172.

[9]張保鋼,時空數據模型在城市測繪數據庫中的應用[博士學位論文].北京:中國地質大學,2005.

[10]李勇,基于GIS-T的城市公共交通時空數據模型研究及其應用[博士學位論文].廣州:中國科學院,2005.

[11]余志文、張利田、鄰永宏,基態(tài)修正時空數據模型的進一步擴展[J].中山大學學報(自然科學版),2004,42(1):100～103.

[12]Langran G.Temporal GIS design trade-offs//Proceedings of GIS/LIS'88[C].San Antonio:ACSM,1988:890～899.

[13]李勇、陳少沛、譚建軍,基于基態(tài)距優(yōu)化的改進基態(tài)修正時空數據模型研究[J].測繪科學,2007,32(1):26～29.