R樹的方向查詢精過濾方法

張澤寶,張健沛,李若愚

(哈爾濱工程大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,黑龍江 哈爾濱 150001)

在空間數(shù)據(jù)庫中,每一個空間對象都有一個與其相對應(yīng)的空間坐標(biāo),空間坐標(biāo)不僅可以表示對象在空間中的位置信息,而且根據(jù)空間坐標(biāo)可以引申出對象之間的空間關(guān)系這一重要概念.空間對象之間的空間關(guān)系主要分為 3大類：距離關(guān)系、拓?fù)潢P(guān)系和方向關(guān)系.在基于拓?fù)潢P(guān)系的查詢方面,KOTHURIR等提出了中間過濾方法,對候選結(jié)果集進(jìn)行 2次過濾[1].BADAWY W等提出利用啟發(fā)式信息來進(jìn)行過濾[2].Rousspoulos[3]等利用測量距離對 R-樹[4]的搜索過程中進(jìn)行有效的剪枝.國防科技大學(xué)的肖予欽[5]等人,定義了一個四元組模型的方向關(guān)系,本文研究的出發(fā)點正是基于四元組模型.為了對復(fù)雜的空間數(shù)據(jù)進(jìn)行高效的查詢,包括 Oracle Spatial在內(nèi)的許多數(shù)據(jù)搜索引擎都使用可分為兩步的查詢過濾方法.第 1步被稱為過濾,使用幾何數(shù)據(jù)的外部近似(如 MBR),外部近似完全包含幾何數(shù)據(jù),過濾通常是利用空間索引[6]來進(jìn)行的.在第 2步的取精過程中,候選數(shù)據(jù)與查詢圖形進(jìn)行精確計算,得出最終的結(jié)果集返回給用戶,這步是空間連接查詢[7]耗時的.

1 方向關(guān)系定義

1.1 MBR之間的方向關(guān)系

為了提高空間數(shù)據(jù)的查詢效率,空間對象通常都是由 MBR來近似表示的.本文所給出的方向關(guān)系是基于四元組模型的：假設(shè)坐標(biāo)系 y軸與 north方向一致,x軸與 east方向一致,兩個空間對象的 MBR分別為 a和 b,一個矩形完全可以由其左下角頂點(axl,ayl)和右上角頂點(axu,ayu)來唯一確定.2個MBR之間的方向關(guān)系完全可以由其在某一坐標(biāo)軸上的投影來確定.采用(N,S)a,b和(E,W)a,b,分別表示 North-South方向和 East-West方向上 a相對于 b的方向關(guān)系,(N,S)a,b,和(E,W)a,b定義如下：

在實際計算中,a和 b在 X軸上的投影之間的關(guān)系決定了(E,W)a,b的取值,下圖為(E,W)a,b定義的直觀解釋,(N,S)a,b同理可知,如圖1所示.

圖1 a,b在 X軸投影間的關(guān)系Fig.1 Relationships between projections of a and b on X-axis

由(N,S)a,b,和(E,W)a,b排列最合可以得到四元組模型 (N,S,E,W)a,b,比如：NorthWest(a,b),其取值為 (1,0,0,1),其他的類似可知.

1.2 對象之間的方向關(guān)系

由于 MBR只是空間對象的近似表示,所以MBR之間的方向關(guān)系并不一定就是空間對象之間的方向關(guān)系.方向關(guān)系矩陣根據(jù)目標(biāo)對象落在參考對象內(nèi)對空間的不同劃分來描述方向[8-10].參考對象把空間劃分為 9個部分：NorthWest(NW),North(N),NorthEast(NE),West(W),Same(O),East(E),SouthWest(SW),South(S)和SouthEast(SE).其表示方法如下所示：

它是一個 3×3的矩陣,其元素保存了空間劃分間的相鄰關(guān)系及目標(biāo)對象和參考對象間的相交情況.其中元素 0表示不相交,元素 1表示相交,若目標(biāo)對象和參考對象的某個空間劃分相交,則它們滿足相應(yīng)劃分所定義的方向關(guān)系.

在具體實現(xiàn)中,采用位段[NwN NE wO E SwS SE]來存儲方向關(guān)系矩陣,即矩陣中每個元素都用 1位表示,這樣可以極大地減少存儲空間.如[0 0 1 0 0 0 0 0 0]表示目標(biāo)對象在參考對象的東北方向,[0 0 0 0 0 0 0 1 1]表示目標(biāo)對象在參考對象的南和東南方向,對于方向關(guān)系矩陣中每個元素取值的判斷,采用幾何計算中多邊形相交的算法就可以解決.

2 方向關(guān)系查詢處理方法

R-樹有一個非常重要的特性,那就是 R-樹中任一結(jié)點所表示的空間區(qū)域必定包含其所有子結(jié)點的空間區(qū)域,正是因為 R-樹具有此特性,因此可采取文獻(xiàn)[5]的剪枝策略對其進(jìn)行 R-樹剪枝.在空間對象的查詢過程中,其實質(zhì)上就是 R-樹的一次遍歷過程,為了達(dá)到提高對空間對象的查詢效率的目的,本文采取了一種剪枝策略,在遍歷過程中,采取一定的剪枝方法來避免搜索那些肯定不在目標(biāo)結(jié)果范圍內(nèi)的結(jié)點,使得訪問結(jié)點分支的數(shù)量減少.根據(jù) R-樹的這個特性,可以得到下面的剪枝策略.如 R-樹中的 2個結(jié)點之間滿足 {NorthEast,NorthWest,South-East,SouthWest}中的任一關(guān)系,那么兩結(jié)點的所有子孫結(jié)點也必定滿足相應(yīng)關(guān)系.

若 2個結(jié)點滿足 {NorthSame,NorthUnknown}中的任一關(guān)系,那么這 2個結(jié)點的子結(jié)點必定滿足如下 4種關(guān)系 {NorthEast,NorthWest,NorthSame,NorthUnknown}之一,其他對象之間的空間關(guān)系可以類推得到,因此要查找所有滿足 NorthWest關(guān)系的空間對象,那么在遍歷 R-樹的過程中,只需要訪問那些中間結(jié)點滿足{NorthWest,NorthSame,NorthUnknown,SameWest,UnknownWest,SameSame,SameUnknown,UnknownSame,UnknownUnknown}中任一關(guān)系才可能得到正確的查詢結(jié)果,而最終搜索到的 2個對象的 MBR之間的關(guān)系必須滿足{NorthUnknown,NorthWest,UnknownUnknown,UnknownWest}之一.顯然,這樣就避免了訪問那些肯定不在目標(biāo)結(jié)果范圍內(nèi)的中間結(jié)點,從而提高了空間對象的查詢效率.

本文在以上的剪枝策略定義基礎(chǔ)上,在過濾步驟和求精步驟之間,插入了一個中間步驟,通過這個中間步驟,對查詢對象進(jìn)行 2次過濾以減少候選集的大小,因此可以很大程度上降低求精步驟的計算代價,通過理論的分析,證明改進(jìn)之后的查詢處理方法具有更高的效率,也通過實例驗證了改進(jìn)的方法可提高查詢處理性能,具體的查詢處理過程如下.

定義中如果一維的空間關(guān)系確定,另外一維方向需要精算來確定空間關(guān)系,如：NorthUnknown,UnknownWest,SameUnknown,UnknownSame,UnknownEast,SouthUnknown.如果得出兩對象之間的方向關(guān)系為 NorthUnknown,那么就可以推斷出 2個實際空間對象 a和 b之間的方向關(guān)系必定滿足{NW(a,b)∧ N(a,b),NW(a,b)∧ N(a,b)∧NE(a,b),N(a,b)∧ NE(a,b)}其中之一,如圖2所示.

從圖2可以很明顯的看出只需要根據(jù)目標(biāo)對象的頂點落在哪一個劃分區(qū)間中,即可判斷出 2個實際對象之間的空間關(guān)系并且得到 2個實際對象之間的方向關(guān)系矩陣.例如對于圖2(b),可以很容易的計算出 a對象的 MBR的左上角頂點和右上角頂點分別落在劃分 NW和劃分 NE中,從而可得出 a相對于 b的空間關(guān)系矩陣為[1 1 1 0 0 0 0 0 0],因而無需再進(jìn)行大量極其復(fù)雜的精確幾何計算,所以極大地提高了查詢效率.其他情況可以類推得到.

圖2 二維舉例Fig.2 Example on two dimensions

3 精過濾查詢處理方法

由于 MBR性質(zhì)和特點可以得到如下的引理.

引理 1 對于 R-樹中非葉子結(jié)點的 MBR,任一MBR的每一個面都至少包含其內(nèi)部空間對象的一個點.如圖3所示.

圖3 非葉子結(jié)點舉例Fig.3 Example on nonleaf node

證明 由 R-樹定義顯然可得.

引理 2 在二維空間中,對于 R-樹中葉子結(jié)點的 MBR,任一 MBR都至少有兩個邊包含其內(nèi)部空間對象的一個點.如圖4所示.

證明 由 MBR定義顯然可得.

當(dāng)在兩維方向上均不能確定對象之間的方向關(guān)系,也就是兩對象之間 MBR的方向關(guān)系滿足 UnknownUnknown.由方向關(guān)系的定義可以得出 UnknownUnknown一共有 25種組合情況,這是因為每一個 Unknown都是由 5種情況組合而成的.而這 25種情況根據(jù)對象a的 MBR所占據(jù)的劃分個數(shù)不同,可以分成 3個大類.如圖5所示.

第1大類一共有16種情況所組成,對象 a的MBR占據(jù) 4個劃分,如圖5(a)所示.

第2大類一共有8種情況所組成,對象 a的MBR占據(jù) 6個劃分,如圖5(b)所示.

第3大類只有1種情況所組成,對象 a的 MBR占據(jù) 9個劃分,如圖5(c)所示.

圖4 葉子結(jié)點舉例Fig.4 Example on leaf nodes

圖5 3類情況舉例Fig.5 Example on three classes

根據(jù)引理 2可以得到空間對象 a與其 MBR至少交于 2點,如果可以確定空間對象與其 MBR的相交點,根據(jù)相交點所處的劃分就可以很容易的判斷出實際空間對象有一部分區(qū)域必定落在該劃分之中,所在精算步驟中可以排除在該劃分中的計算,從而大大減少了計算代價.

相交點的計算是十分簡便的,因為根據(jù)MBR的定義和引理 2可知,在求解空間對象的 MBR的同時也會得到空間對象與其 MBR的相交點,當(dāng)求出相交點之后,即可得出空間對象必定落在某個劃分之中,從而無需復(fù)雜的取精操作,而對于剩下的劃分,需要做的只是把對象 MBR和該劃分的交集(必定為一個矩形)與空間對象進(jìn)行比較,看其是否落在該交集之內(nèi),這就將兩個空間對象的計算問題轉(zhuǎn)化為了一個窗口查詢的問題,相對于計算 2個空間對象之間的關(guān)系,窗口查詢的效率更高,所付出的代價更小.

本文在傳統(tǒng)的過濾方法過程中加入了一個中間步驟,通過理論推導(dǎo)可以得出,對傳統(tǒng)方法改進(jìn)之后算法的性能得到了很大的提升.

證明過程：本文算法假設(shè),某一種情況在單個象限上進(jìn)行取精操作的權(quán)值為 1,而各個空間對象是服從均勻分布的.根據(jù)每種情況出現(xiàn)的次數(shù)和概率進(jìn)行證明,下面為其證明過程,其中傳統(tǒng)的查詢過濾方法為 TQFM,改進(jìn)的查詢過濾方法為 IQFM.

TQFM方法：

1)在兩個方向上均需要執(zhí)行取精操作的是(UnknownUnknown)的情況,在傳統(tǒng)定義中有 5種空間位置關(guān)系被定義為 Unknown,而每種情況均需要在各個象限上進(jìn)行取精的操作,所以在 UnknownUnknown情況下的算法耗費為 121,即

第 1大類：16×4=64

第 2大類：8×6=48

第 3大類：1×9=9

所以總耗費為：16×4+8×6+1×9=121.

2)僅在單個方向上進(jìn)行取精操作的有：(Same-Unknown,UnknownSame,NorthUnknown,SouthUnknown,UnknownWest,UnknownEast)6種關(guān)系謂詞,每一種謂詞對應(yīng)了 3種情況,如圖2所示,3種情況共需要在 7個劃分上進(jìn)行精算操作,所以在單個方向精算的耗費為 42,即

6×(2+2+3)=42.

TQFM方法的總耗費為：121+42=163.

IQFM方法：

由引理 2可知,空間對象與其 MBR至少有 2個相交點,在這里假設(shè)最壞的情況,即每一個空間對象與其 MBR有 2個相交點,也就是可以確定空間對象存在于某 2個劃分之中,從而減少 2個劃分的求精計算.

1)在 2個方向上都需要執(zhí)行取精操作

(UnknownUnknown)：

第1大類：16×(4-2)=32

第2大類：8×(6-2)=32

第3大類：1×(9-2)=7

所以總耗費為：16×2+8×4+1×7=71.

2)在單個方向上無需進(jìn)行取精操作(因為通過判斷對象在某一維上的極值點落在哪一個劃分內(nèi),即可確定其跨越的劃分情況,同時其 9元組也隨之得到 )：(SameUnknown,UnknownSame,NorthUnknown,SouthUnknown,UnknownWest,UnknownEast).

IQFM方法的總耗費為：71+0=71.

由上可得：IQFM/TQFM=43.5%,改進(jìn)的方法需要精算的算法耗費僅為傳統(tǒng)方法的 43.5%,減少了大量的精算數(shù)據(jù)集,性能得到了很大的提升.

4 實驗設(shè)計與性能評估

4.1 實驗環(huán)境

前面已經(jīng)理論分析論證了算法的有效性,現(xiàn)在通過實驗來對算法的性能進(jìn)行評估.實驗平臺：

操作系統(tǒng)：Windows2 000 Professional

CPU：1.70GHz

內(nèi)存：256M

編程環(huán)境：Visual C++6.0

4.2 實驗示例與總結(jié)

在仿真實驗中本文使用美國國家統(tǒng)計局所提供的 TIGER/Line圖形文件[11],它是測試空間連接算法的標(biāo)準(zhǔn)數(shù)據(jù)集.TIGER/Line圖形文件來自于美國國家統(tǒng)計局的 MAF/TIGER數(shù)據(jù)庫,它包含了公路、鐵路、河流等地理信息.TIGER/Line圖形文件是對外公開并且是完全免費的,通常用來為地理信息系統(tǒng)(GIS)或繪圖軟件提供數(shù)字地圖.本文選取哥倫比亞地區(qū)的道路和街區(qū)作為 2個輸入數(shù)據(jù)集,前者包含 15 141個線對象,后者包含 5 665個面對象.本文為每個數(shù)據(jù)集創(chuàng)建了頁面大小 1 kB的 R-樹,葉結(jié)點存儲的是對象的 MBR.

先來看一下在使用單個連接謂詞情況下,使用改進(jìn)的查詢過濾方法(IQFM)與傳統(tǒng)的查詢過濾方法(TQFM)的性能比較,磁盤的訪問次數(shù)和執(zhí)行時間如表1所示.

表1 I/O訪問次數(shù)和比較次數(shù)Table 1 Number of I/O and number of comparisons

接下來,看一下在綜合情況下,使用改進(jìn)的查詢過濾方法與傳統(tǒng)的查詢過濾方法進(jìn)行的性能比較,對比結(jié)果如圖6、圖7所示.其中,DT為 Disk Time,RT為 Response Time,QR為 Query Radius.

圖6 I/O比較Fig.6 Comparison of I/O

圖7 執(zhí)行時間比較Fig.7 Comparison of response time

圖6和圖7是針對磁盤的訪問次數(shù)和算法的執(zhí)行時間 2個重要的算法性能指標(biāo),這是衡量算法質(zhì)量的兩個重要因素.所以本文就將磁盤的訪問次數(shù)和算法執(zhí)行時間來分別作為實驗結(jié)果的衡量標(biāo)準(zhǔn).

圖6的橫坐標(biāo)表示的是查詢半徑,縱坐標(biāo)表示的是磁盤的訪問次數(shù).從圖中可以明顯的看到,當(dāng)查詢半徑小于 0.5 km的時候,使用新的過濾方法與不使用新過濾方法相比磁盤的訪問次數(shù)基本上是相同的,都在 47次左右.而當(dāng)查詢半徑大于 1 km時,使用新的過濾方法對磁盤的訪問次數(shù)要明顯的小于不使用新的過濾方法.這主要是因為在查詢半徑比較小的情況下,查詢范圍內(nèi)的目標(biāo)對象也是非常少的,所以并不能很好的體現(xiàn)出兩種方法之間的差異,而當(dāng)查詢范圍逐漸增大的時候,范圍內(nèi)的目標(biāo)對象也隨之增多,新的過濾方法對查詢性能的影響逐漸增大,所以新的過濾方法對磁盤的訪問次數(shù)要明顯的小于之前的方法,從而新的方法顯示出了更好的查詢性能.在圖7中,之所以當(dāng)查詢半徑小于 0.5 km時 2個算法的執(zhí)行時間十分的接近,其原因上面已經(jīng)解釋過.所以,新的方法不僅僅是在理論上可行的,在實際中對空間查詢也可以起到很好的優(yōu)化作用.

5 結(jié)束語

對空間對象的方向關(guān)系模型進(jìn)行了分析,根據(jù)在各坐標(biāo)軸上的投影,分析對象之間的關(guān)系,給出了方向關(guān)系矩陣,分析了方向關(guān)系查詢處理方法,給出了查詢處理過程的剪枝策略,提出了一種新的查詢過濾方法.該方法通過參考對象對空間進(jìn)行劃分,根據(jù)目標(biāo)對象與其 MBR的交點是否落在某個劃分中即可判斷出該目標(biāo)對象的具體位置,從而確定出目標(biāo)對象和參考對象之間的多種可能的方向關(guān)系,通過此方法進(jìn)行過濾,減少了精確計算的數(shù)據(jù)量.通過理論的分析和實際的試驗表明,查詢時間和磁盤訪問的次數(shù)分別提高了 40%和 20%左右.

[1]KOTHURI R,RAVADA S.Efficient Processing of large spatial queries using interior approximation[C]//Proceedings of the 7th International Symposiumon Advances in Spatial and Temporal Database.Redondo Beach,CA,USA,2001：404-421.

[2]BADAWY wM,GAREF W.On local heuristics to speed uppolygon-polygon intersection tests[C]//Proceedings of the 7th International Symposiumon Advances in Geographic Information Systems.Kansas City,USA,1999：97-102.

[3]ROUSSPOULOS N,KELLY S,VINCENT F.Nearest neighbor queries[C]//Proceedings of the ACmSIGMOD International Conference on the Management of Data.San Jose,CA,USA,1995：71-79.

[4]GUTTMAN A.R-trees：a dynamic index structure for spatial searching[C]//Proc.of International Conference on Managementof Data.Boston,USA,1984：47-54.

[5]肖予欽,張巨,景寧,李軍.基于R樹的方向關(guān)系查詢處理[J].軟件學(xué)報,2004,15(1)：103-111.XIAO Yuqin,ZHANG Ju,JING Ning,LI Jun.Direction relation query processing using R-trees[J].Journal of Software,2004,15(1)：103-111.

[6]郭薇,郭菁,胡志勇.空間數(shù)據(jù)庫索引技術(shù)[M].上海：上海交通大學(xué)出版社,2006：1-7.GUO Wei,GUO Jing,HU Zhiyong.Indexing techniques for spatial database[M].Shanghai：Shanghai Jiao Tong University Press,2006：1-7.

[7]李俊潔,郝忠孝.基于柵格的空間連接查詢[J].哈爾濱理工大學(xué)學(xué)報,2008,13(2)：1-4.LIJunjie,HAO Zhongxiao.Spatial join query based raster signatures[J].Journal of Harbin University of Science and Technology,2008,13(2)：1-4.

[8]GOYAL R K,EGENHOFER mJ.Similarity of cardinal directions[C]//Proc of the SSTD 2001.Lecture Notes in Computer Science 2121.Berlin：Springer-Verlag,2001：33-55.

[9]曹菡,陳軍,杜道生.空間目標(biāo)方向關(guān)系的定性擴(kuò)展描述[J].測繪學(xué)報,2001,30(2)：162-167.CAO Han,CHEN Jun,DU Daosheng.Qualitativeextension description for cardinal directions of spatialobjects[J].Acta Geodaetica et Cartographica Sinica,200l,30(2)：l62-167.

[10]馮玉才,陳琳,曹忠升.空間數(shù)據(jù)庫的方向關(guān)系模型[J].計算機(jī)工程與應(yīng)用,2001,20：115-l 17.FENG Yucai,CHEN Lin,CAOZhongsheng.Direction relation model of spatial database[J].Computer Engineering and Applications,2001,20：115-l 17.

[11]US Bureau of the Census.Census 2000 TIGER/Line files[EB/OL].(2000-08-05).http：//www.census.gov.