周 侗,龍 毅,湯國安,胡雷地

(1.南通大學(xué)地理科學(xué)學(xué)院,江蘇南通 226007;2.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210046）

面向集聚分布空間數(shù)據(jù)的混合式索引方法研究

周 侗1,龍 毅2,湯國安2,胡雷地2

(1.南通大學(xué)地理科學(xué)學(xué)院,江蘇南通 226007;2.南京師范大學(xué)虛擬地理環(huán)境教育部重點(diǎn)實(shí)驗(yàn)室,江蘇南京 210046）

空間數(shù)據(jù)索引技術(shù)可以有效地提高空間數(shù)據(jù)在存儲(chǔ)、處理、分析以及地圖可視化中的效率,其性能優(yōu)劣直接影響GIS的整體性能。該文針對格網(wǎng)索引和四叉樹索引存在的問題,提出將四叉樹嵌入格網(wǎng)形成一種混合式空間索引結(jié)構(gòu),并分析其原理、數(shù)據(jù)結(jié)構(gòu)與影響參數(shù)。理論分析及實(shí)驗(yàn)證明,對于空間集聚分布狀態(tài)的海量地理數(shù)據(jù)而言,混合式索引方法以略高的存儲(chǔ)代價(jià)換取了更高的檢索、插入和刪除效率,是一種有效的空間索引方案。

混合索引;空間索引;GIS;地圖可視化

目前,GIS技術(shù)廣泛應(yīng)用于空間相關(guān)的各領(lǐng)域,但也產(chǎn)生了一系列新問題,如數(shù)據(jù)量日益膨脹、空間分析過程復(fù)雜化等[1]?？臻g數(shù)據(jù)存儲(chǔ)與操作成為限制GIS發(fā)展的瓶頸問題之一,空間索引技術(shù)是一種常見的解決方案,其提供了一種快速、有選擇性地存取數(shù)據(jù)庫的機(jī)制,相當(dāng)于一個(gè)映射機(jī)構(gòu),將屬性值轉(zhuǎn)換為相應(yīng)記錄的地址或地址集[2]。GIS的空間分析與可視化過程,往往涉及多次重復(fù)耗時(shí)、復(fù)雜的幾何操作以及大量的磁盤存取過程,沒有一種合理空間數(shù)據(jù)索引方案的支持,必將直接影響系統(tǒng)運(yùn)行的效率。前期實(shí)驗(yàn)表明,空間索引方案和數(shù)據(jù)的空間分布類型具有一定的聯(lián)系,暫時(shí)沒有一種方案適用于所有類型的空間數(shù)據(jù),對于集聚分布狀態(tài)的空間數(shù)據(jù)而言,使用已有的空間索引方案很難達(dá)到預(yù)期效果。本文總結(jié)了部分已有方案的特點(diǎn),在此基礎(chǔ)上提出了基于格網(wǎng)和四叉樹的混合空間索引方案。

1 典型空間索引結(jié)構(gòu)

1.1 格網(wǎng)索引

格網(wǎng)索引是規(guī)則地劃分二維數(shù)據(jù)空間,得到m ×n個(gè)矩形網(wǎng)格區(qū)域(圖1a）,每個(gè)網(wǎng)格區(qū)域?yàn)橐粋€(gè)索引項(xiàng),并分配一個(gè)動(dòng)態(tài)存儲(chǔ)區(qū),全部或部分落入該網(wǎng)格的空間對象的標(biāo)識以及外接矩形存入該網(wǎng)格[3]。當(dāng)用戶進(jìn)行空間查詢等操作時(shí),首先計(jì)算出擬查詢的空間對象所在的網(wǎng)格,然后在該網(wǎng)格中快速查詢所選空間對象。規(guī)則網(wǎng)格空間索引是一種分割空間對象的索引方法,其原理簡單、操作簡潔、可以直接訪問,在涉及的數(shù)據(jù)量不大、不需復(fù)雜的空間操作時(shí),具有一定的適用性。但在建立索引前需要預(yù)知空間目標(biāo)所覆蓋的范圍,可調(diào)節(jié)性相對較差。此外,網(wǎng)格劃分的精細(xì)程度取決于地理對象的大小、數(shù)量、分布及建庫人員的經(jīng)驗(yàn),網(wǎng)格劃分過于粗略,每個(gè)網(wǎng)格內(nèi)可能包含大量地理對象,搜索精度不高;網(wǎng)格劃分過細(xì),雖然可以提高搜索精度,但一個(gè)對象會(huì)落入多個(gè)網(wǎng)格中,導(dǎo)致數(shù)據(jù)處理過程出現(xiàn)冗余現(xiàn)象。

圖1 集聚分布點(diǎn)群的格網(wǎng)索引與四叉樹索引Fig.1 Gridsand Quadtrees index structure of the aggregated point sets

1.2 四叉樹索引

四叉樹是建立在對區(qū)域循環(huán)分解原則上的一種層次數(shù)據(jù)結(jié)構(gòu),在計(jì)算機(jī)圖形學(xué)、圖像處理以及 GIS領(lǐng)域得到了廣泛應(yīng)用,也適用于對空間數(shù)據(jù)的表示和索引[4-7]。如圖1b所示,它是一種面向空間地理對象的空間索引技術(shù),將空間區(qū)域逐次劃分為4個(gè)等大的子區(qū)域,劃分的最大層次由用戶指定。四叉樹的每個(gè)節(jié)點(diǎn)有0個(gè)或4個(gè)子節(jié)點(diǎn),每個(gè)子節(jié)點(diǎn)代表父節(jié)點(diǎn)的一個(gè)子區(qū)域。節(jié)點(diǎn)通常需要存放其所表示的空間區(qū)域范圍和屬于該節(jié)點(diǎn)的空間對象的標(biāo)識(ID）。

四叉樹索引結(jié)構(gòu)是一種清晰、容易建立的層次數(shù)據(jù)結(jié)構(gòu),其具有如下特點(diǎn):1）通常使用順序存儲(chǔ)的線性表表示索引,內(nèi)存需求量小,使空間查詢速度得到提升;2）插入和刪除操作簡便,平均耗時(shí)遠(yuǎn)小于R樹。但由于其以空間劃分來組織索引結(jié)構(gòu)的索引機(jī)制,當(dāng)數(shù)據(jù)量較大時(shí),四叉樹劃分的層數(shù)過少,將導(dǎo)致查詢性能的下降;劃分的層數(shù)過多,將導(dǎo)致存儲(chǔ)的冗余,從而增加空間開銷,影響查詢性能。

1.3 其他索引方法

常見的索引方法還有范圍索引、R樹、B樹、QR樹等,其原理不再贅述;部分學(xué)者嘗試將已有的索引方法相結(jié)合,取得一定的成效[8-12]。本文在對集聚分布數(shù)據(jù)的可視化實(shí)驗(yàn)中,嘗試使用不同的空間索引方案,發(fā)現(xiàn)索引方法的效率受空間數(shù)據(jù)分布類型的影響,僅將一種空間索引方法應(yīng)用于數(shù)據(jù)管理,有時(shí)難以大幅度提高系統(tǒng)運(yùn)行效率。

2 空間數(shù)據(jù)的分布對索引的影響

2.1 空間數(shù)據(jù)分布的類型

地圖點(diǎn)群的空間分布通常分為均勻分布、隨機(jī)分布和集聚分布3種類型。均勻分布即點(diǎn)群在地圖每個(gè)區(qū)域的分布數(shù)量相同或相似,如社區(qū)內(nèi)建筑物的分布;集聚分布主要是點(diǎn)群圍繞單核或多核呈簇狀分布,主要表現(xiàn)為點(diǎn)群集中分布于整個(gè)區(qū)域的個(gè)別區(qū)域,如本實(shí)驗(yàn)所采用的南京地區(qū)企事業(yè)單位點(diǎn)群數(shù)據(jù);隨機(jī)分布則介于均勻分布和集聚分布之間。

2.2 數(shù)據(jù)分布類型對索引方法效率的影響

均勻分布的地理數(shù)據(jù),當(dāng)采用格網(wǎng)索引時(shí),數(shù)據(jù)均勻地分布于格網(wǎng)的每個(gè)單元中,因而格網(wǎng)索引的效率相對較高,基本不存在數(shù)據(jù)冗余,即包含地理對象數(shù)目較少的單元格不會(huì)大量出現(xiàn);對于四叉樹索引類型而言,葉子單元中的對象數(shù)目上限設(shè)置較為合理,空間索引效率較高。因而,均勻分布的空間數(shù)據(jù)對于空間索引方法的依賴性較弱,只要索引方法應(yīng)用合理,一般運(yùn)行效率較高。

而對于集聚分布的點(diǎn)群,以單核的簇狀分布為例(多核的集聚分布點(diǎn)群情況與其類似）,當(dāng)采用格網(wǎng)索引時(shí)(圖1a）,對集聚分布的點(diǎn)群進(jìn)行m×n格網(wǎng)劃分,當(dāng)m、n的值較小時(shí),格網(wǎng)索引劃分的效果不明顯,沒有達(dá)到索引的目的;當(dāng)m、n的值過大時(shí),導(dǎo)致格網(wǎng)過多,但是集聚分布的點(diǎn)群仍分布在少數(shù)格網(wǎng)中,不僅降低了索引效率,而且造成了冗余。采用四叉樹索引時(shí)(圖1b）,當(dāng)?shù)乩韺ο髷?shù)量較多時(shí),四叉樹所劃分的層數(shù)也較多,但隨著層數(shù)的增加,深度越大,四叉樹索引的效率就會(huì)降低。由此可見,此分布類型受空間索引方案的影響較為明顯,使用不當(dāng)時(shí)很難提高系統(tǒng)運(yùn)行效率。

隨機(jī)分布點(diǎn)群對于索引方法效率的影響介于均勻分布和集聚分布類型之間?；谝陨戏治?對于解決集聚分布的空間數(shù)據(jù),四叉樹索引和格網(wǎng)索引方法均有不足之處,難以滿足效率和冗余度等方面的要求。而將四叉樹索引嵌入格網(wǎng)索引中,可以部分消除兩者的短板,形成一種新型的混合空間索引方案,一定程度上可提高操作效率,減少數(shù)據(jù)冗余,大大提高了數(shù)據(jù)查詢的性能。

3 混合索引方法

3.1 索引機(jī)制

3.1.1 原理 首先對研究區(qū)域中的地理對象進(jìn)行格網(wǎng)劃分,檢查每個(gè)格網(wǎng)中地理對象的數(shù)量,如果其滿足閾值要求,說明已達(dá)索引目的,可結(jié)束索引;如果某些網(wǎng)格中地理對象的數(shù)量超過規(guī)定的閾值,需進(jìn)一步對這些地理對象進(jìn)行四叉樹劃分,直到四叉樹的葉子單元中的對象數(shù)量達(dá)到規(guī)定的閾值為止。如圖2所示,當(dāng)?shù)乩韺ο竺芗胤植荚谌舾蓚€(gè)格網(wǎng)中時(shí),仍需對其進(jìn)行四叉樹劃分,直到每層中地理對象的數(shù)量達(dá)到規(guī)定的閾值為止。

圖2 混合索引示意Fig.2 Hybrid index structure for spatial data

3.1.2數(shù)據(jù)結(jié)構(gòu)

(1）格網(wǎng)數(shù)據(jù)結(jié)構(gòu)。網(wǎng)格編碼的整體存儲(chǔ)策略可將網(wǎng)格編碼的所有信息存入一個(gè)64位的長整型數(shù)中,計(jì)算時(shí)可直接使用位運(yùn)算符提取行號、列號和Morton碼,效率較高。但由于標(biāo)識位的存在,提取Morton的效率會(huì)有所降低。因此,可采用有冗余的網(wǎng)格編碼整體存儲(chǔ)策略,即將網(wǎng)格Morton的級數(shù)直接存儲(chǔ)在該編碼中,使得能夠直接根據(jù)級數(shù)判斷Morton碼的長度,而不需在計(jì)算過程中判斷標(biāo)識位。

(2）四叉樹數(shù)據(jù)結(jié)構(gòu)。四叉樹索引具體的實(shí)現(xiàn)方法為規(guī)定一個(gè)閾值,如果當(dāng)前象限中的地理數(shù)據(jù)數(shù)目超過規(guī)定閾值,則需進(jìn)一步劃分,否則結(jié)束索引過程。定義的四叉樹結(jié)構(gòu)體如下:

這里,定義4個(gè)葉子節(jié)點(diǎn)分別指向4個(gè)子區(qū)域,i _num為某節(jié)點(diǎn)所包含的點(diǎn)數(shù)。

3.2 影響參數(shù)

3.2.1 格網(wǎng)索引的分塊數(shù) 格網(wǎng)索引的分塊數(shù)m、n決定了格網(wǎng)劃分的精細(xì)程度,因此也就成為選擇四叉樹索引的重要影響因素。在空間地理對象非均勻分布的前提下,若m、n的值較小,格網(wǎng)的數(shù)量較少,此時(shí)需對分布較密的地理對象建立四叉樹索引;若m、n的值相對較大,說明格網(wǎng)的劃分較精細(xì),基本上每個(gè)格網(wǎng)中包括的地理對象都在規(guī)定的閾值范圍內(nèi),不需再進(jìn)行四叉樹劃分。

3.2.2 四叉樹節(jié)點(diǎn)的閾值 當(dāng)對地理對象進(jìn)行格網(wǎng)劃分時(shí),需要設(shè)定閾值以確定劃分的最小單元。由于閾值的大小對于空間索引的效率會(huì)產(chǎn)生一定的影響,因此閾值的確定要根據(jù)實(shí)際地理對象的分布而定。在格網(wǎng)索引中,閾值的大小一般是指網(wǎng)格的數(shù)量m、n,此參數(shù)會(huì)影響混合索引的實(shí)現(xiàn)。在四叉樹索引中,閾值是指當(dāng)?shù)乩韺ο蟮臄?shù)目達(dá)到該值時(shí)四叉樹不再細(xì)分,因而此參數(shù)直接決定了四叉樹的層數(shù):閾值過大,層數(shù)相對較少,空間劃分不徹底;閾值過小,層數(shù)相對較多,增加了四叉樹的深度,造成數(shù)據(jù)冗余,會(huì)降低空間索引的效率。

4 實(shí)驗(yàn)結(jié)果及驗(yàn)證

為了進(jìn)一步驗(yàn)證各種空間索引方式在地理信息系統(tǒng)中的作用,本文以地圖可視化為例進(jìn)行實(shí)驗(yàn)。

4.1 地圖可視化實(shí)驗(yàn)

4.1.1 實(shí)驗(yàn)平臺 實(shí)驗(yàn)采用神達(dá)掌上電腦 P350, CPU為400 M Hz,內(nèi)存為256 M。實(shí)驗(yàn)平臺為M icrosoft Visual Studio2005,開發(fā)語言為 C?。由于移動(dòng)設(shè)計(jì)在硬件水平上存在著瓶頸,當(dāng)處理的地理數(shù)據(jù)量達(dá)到一定程度時(shí),效率明顯降低,并且存在存儲(chǔ)空間有限等不足,致使海量地圖數(shù)據(jù)的可視化受到一定的限制。通過多組實(shí)驗(yàn)證明,基于此種硬件條件,當(dāng)?shù)乩韺ο蟮臄?shù)目超過2萬時(shí),數(shù)據(jù)的顯示更新速度會(huì)明顯下降,因而考慮應(yīng)對地理數(shù)據(jù)建立空間索引方案。本文基于移動(dòng)設(shè)備,采用南京市全區(qū)的地理數(shù)據(jù)進(jìn)行多組地圖可視化實(shí)驗(yàn)。

4.1.2 實(shí)驗(yàn)數(shù)據(jù) 采用南京市的1∶2萬地圖數(shù)據(jù),地域范圍覆蓋了玄武區(qū)、鼓樓區(qū)、建鄴區(qū)、白下區(qū)、秦淮區(qū)、下關(guān)區(qū)、雨花臺區(qū)、浦口區(qū)、棲霞區(qū)、江寧區(qū)、六合區(qū)、溧水縣、高淳縣13個(gè)區(qū)(縣）等,主要包括點(diǎn)、線、面3種數(shù)據(jù)類型(點(diǎn)數(shù)據(jù)包括景點(diǎn)、企事業(yè)單位、賓館、酒店等,線狀地物包括道路、河流、城墻、行政界線等,面狀地物包括街區(qū)、綠地、湖泊等）;3類地物數(shù)量共為43 551,從整個(gè)地域范圍上看,數(shù)據(jù)呈典型的多核集中分布狀態(tài),集中在南京的城區(qū)及縣(區(qū)）的城鎮(zhèn)中心周圍(圖3）。實(shí)驗(yàn)分為3組,分別采用格網(wǎng)索引、四叉樹索引及混合索引結(jié)構(gòu),并對南京全區(qū)的地理數(shù)據(jù)建立混合空間索引方式(圖4）。

圖4 南京地圖數(shù)據(jù)的混合空間索引方式Fig.4 The hybrid index structure for spatial data of Nanjing

圖3 實(shí)驗(yàn)數(shù)據(jù)示意Fig.3Experimental data

4.2 實(shí)驗(yàn)結(jié)果驗(yàn)證

本文空間索引的地圖可視化測試運(yùn)行速度采用監(jiān)測系統(tǒng)時(shí)間的方法確定。但是執(zhí)行同類操作(如放大、漫游等）,由于地圖數(shù)據(jù)在屏幕區(qū)域上顯示的范圍不同,因而每步操作處理的空間數(shù)據(jù)量不固定,系統(tǒng)運(yùn)行時(shí)間也不同。本文采用相對定性的方法表示每種空間索引方法的運(yùn)行效率,用多組實(shí)驗(yàn)的平均時(shí)間作為各種方法的評價(jià)標(biāo)準(zhǔn),實(shí)驗(yàn)結(jié)果如表1所示?？梢钥闯?采用混合空間索引機(jī)制相比單一的空間索引方式具有明顯優(yōu)勢。

表1 南京地圖數(shù)據(jù)的地圖操作效率Table 1 Efficiency comparison of different index structures used in the spatial data of Nanjing

5 結(jié)語

本研究構(gòu)建了基于四叉樹索引和格網(wǎng)索引的混合索引結(jié)構(gòu),并通過基于移動(dòng)設(shè)備的南京市全區(qū)地理數(shù)據(jù)可視化實(shí)驗(yàn),證明混合索引結(jié)構(gòu)對于集聚分布的地理數(shù)據(jù)而言,較單純的四叉樹索引和格網(wǎng)索引具有明顯優(yōu)勢,其以略高的存儲(chǔ)代價(jià)換取了更高的檢索、插入和刪除效率,特別是可以大大提升海量數(shù)據(jù)的索引性能。但本文僅提出了混合索引的構(gòu)建方法及在集聚空間數(shù)據(jù)可視化中的應(yīng)用,探討了幾個(gè)控制參數(shù)的地理含義,還需進(jìn)一步研究其機(jī)理,以便應(yīng)用于不同類型的空間數(shù)據(jù)中,提高空間數(shù)據(jù)分析及顯示效率。

[1] 陳菲,秦小麟.空間索引的研究[J].計(jì)算機(jī)科學(xué),2001,28:59-62.

[2] 黃杏元,馬勁松.地理信息系統(tǒng)概論(第三版）[M].北京:高等教育出版社,2008.136-138.

[3] 張麗芬,王曉華,胡景松,等.基于網(wǎng)格劃分的幾種空間索引[J].北京理工大學(xué)學(xué)報(bào),2004,24(2）:140-144.

[4] GAEGAN M.A efficient use of Quadtrees in a geographical info rmation system[J].Int.J.GIS,1989,3(3）:32-43.

[5] 董鵬,李津平,白予琦,等.基于改進(jìn)四叉樹索引的矢量地圖疊加分析算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(4）: 530-534.

[6] 董鵬,楊崇俊,芮小平,等.一種基于改進(jìn)四叉樹的 GIS空間選擇查詢算法——以ESRISHAPE格式文件為例[J].計(jì)算機(jī)工程與應(yīng)用,2003(13）:58-61.

[7] 袁達(dá).一種新的線性四叉樹編碼的研究[J].測繪科學(xué),1990 (4）:1-4.

[8] 徐少平,王命延,王煒立.一種基于R樹和四叉樹的移動(dòng)對象空間數(shù)據(jù)庫混合索引結(jié)構(gòu)[J].計(jì)算機(jī)與數(shù)字工程,2005,34:54-57.

[9] 黃明,陳哲.基于改進(jìn)QR-樹的空間數(shù)據(jù)索引的研究[J].黑龍江工程學(xué)院學(xué)報(bào)(自然科學(xué)版）,2005,9(3）:18-20.

[10] 吳敏君,郭永洪,陳天滋.一種有效的混合空間索引機(jī)制[J].計(jì)算機(jī)工程與應(yīng)用,2006,29:193-197.

[11] 吳煥萍,潘懋,胡金星,等.基于空間索引的規(guī)則格網(wǎng)DTM內(nèi)插算法研究[J].地理與地理信息科學(xué),2004,20(1）:43-46.

[12] 何小苑,閔華清.基于聚類的 Hilbert R-樹空間索引算法[J].計(jì)算機(jī)工程,2009,35(9）:40-42.

Research on the Hybrid Index Structure for Aggregated Spatial Data

ZHOU Tong1,LONG Yi2,TANG Guo-an2,HU Lei-di2
(1.School of Geographic Science,Nantong University,N antong226007;2.Key Laboratory of Virtual Geographical Environment,M inistry of Education,N anjing N ormal University,N anjing210046,China）

Studies on spatial data distribution and index structure have found that neither grid nor quadtree index structure is efficient fo r managing the aggregated spatial data.In case of the grid index structure,either the majo rity of the data is located in very few grids o r too detailed carving-up w ill lead to many grids,thus resulting in data redundancy.The only emp loyment of quadtree index structure is also unsatisfacto ry since data concentration w ill lead to the quadtree dep th increase,thus undermining index efficiency.Based on the advantagesof the aforementioned two structures,a spatial hybrid index structure is p roposed in this paper,w hich adop ts the grid index structure for the larger scale and then comp lements it by inserting quadtree index structure into it per parameters requirement.After a p reliminary analysis of its efficiency,details are given about how to construct such a hybrid index structure and to control its parameters.Within the experiment of this paper,the grid index structure adop ts a coding strategy w ith redundant data,w ith linear top-dow n quadtree index structure inserted.The two main parameters of the hybrid index structure are the resolution and the quadtree threshold respectively,w ith the former determining the number of quadtrees and the latter meaning the threshold num ber of geographical objects in a quadrant,w hen the quadtree w ill stop carving up.Both the grid resolution and the quadtree threshold shall be set in line w ith the distributing feature of geographical spatial data.The hybrid index structure is app lied to visualizing the spatial data of Nanjing City obtained from portable navigating devices.The research result show s that the hybrid index structure enjoysobvious efficiency superio rity over singular ones. Then it is concludes w ith recommendations fo r further study on inner mechanism of the hybrid structure,so as to enhance its stability and sp read its app lication.

hybrid index structure;spatial index structure;GIS;map visualization

P208

A

1672-0504(2010）01-0007-04

2009-08-18;

2009-10-23

國家863計(jì)劃項(xiàng)目(2007AA 12Z218）;國家自然科學(xué)基金(40571120）;南通大學(xué)自然基金(07z114）

周侗(1978-）,男,碩士,講師,從事GIS原理與制圖綜合方面的研究。E-mail:zhoutong@ntu.edu.cn