基于動態變粒度的改進基態修正模型研究

姚茂華　周文婷

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

[關鍵詞]時態GIS 時空數據模型 基態修正 時空數據檢索

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

一、引言

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

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

二、基態修正模型特點

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

三、基態修正模型的改進方法

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

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

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

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

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

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

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

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

四、動態變粒度的改進基態修正模型

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

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

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

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

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

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

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

五、時空檢索

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

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

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

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

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

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

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

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

六、結論

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

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

參考文獻:

[1]劉睿、周曉光,一種基于動態基態方法的時空數據模型擴展[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]張祖勛、黃明智,時態GIS數據結構的探討[J].測繪通報,1996(1):19-22.

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

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

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

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

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

[11]余志文、張利田、鄰永宏,基態修正時空數據模型的進一步擴展[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]李勇、陳少沛、譚建軍,基于基態距優化的改進基態修正時空數據模型研究[J].測繪科學,2007,32(1):26～29.