并行環(huán)境下基于圖著色理論的空間數(shù)據(jù)部署

殷君茹,唐小明,李惺穎,卜祥亮

(1.中國(guó)林業(yè)科學(xué)研究院 資源信息研究所,北京100091;2.廣西林業(yè)勘測(cè)設(shè)計(jì)院 3S技術(shù)研究與開發(fā)中心,南寧 530011;3.北京林業(yè)大學(xué) 水土保持學(xué)院,北京 100083)

?

并行環(huán)境下基于圖著色理論的空間數(shù)據(jù)部署

殷君茹1,唐小明1,李惺穎2,卜祥亮3

(1.中國(guó)林業(yè)科學(xué)研究院 資源信息研究所,北京100091;2.廣西林業(yè)勘測(cè)設(shè)計(jì)院 3S技術(shù)研究與開發(fā)中心,南寧 530011;3.北京林業(yè)大學(xué) 水土保持學(xué)院,北京 100083)

在面向計(jì)算部署到數(shù)據(jù)節(jié)點(diǎn)端執(zhí)行的分布式并行環(huán)境下,提出一種基于圖著色理論的適用于矢量空間數(shù)據(jù)的部署方法,將空間數(shù)據(jù)粒度的部署問題轉(zhuǎn)化為圖頂點(diǎn)著色的過程,提高了任意空間區(qū)域的信息查詢效率.給出基于圖著色理論的數(shù)據(jù)部署方法,并通過節(jié)點(diǎn)的任務(wù)量進(jìn)一步改進(jìn)算法,使得該算法可實(shí)現(xiàn)海量空間數(shù)據(jù)粒度的離散化部署,提高了空間數(shù)據(jù)檢索和查詢的并行化程度,充分利用了并行計(jì)算資源.

空間數(shù)據(jù)部署；數(shù)據(jù)粒度；并行環(huán)境；圖著色理論；負(fù)載均衡

并行計(jì)算環(huán)境下的空間數(shù)據(jù)部署一般都采用“分而治之”的思想,按照一定的規(guī)則將海量空間數(shù)據(jù)均衡分配存放在多個(gè)節(jié)點(diǎn)中,從而達(dá)到多節(jié)點(diǎn)、多處理器協(xié)同工作,提高空間數(shù)據(jù)的快速查詢響應(yīng)和并行分析能力[1-3].

空間數(shù)據(jù)部署(用于任務(wù)劃分和負(fù)載均衡控制)是影響并行地理信息系統(tǒng)(GIS)的關(guān)鍵因素,目前研究多集中在海量事務(wù)性數(shù)據(jù)上,采用主流的分布式文件系統(tǒng)(如GFS,Hadoop,Cassandra,Dynamo和Apache Spark)進(jìn)行管理,按照一致性Hash策略將數(shù)據(jù)均分為大小相同的數(shù)據(jù)塊,并對(duì)每個(gè)塊進(jìn)行隨機(jī)部署,實(shí)現(xiàn)了海量數(shù)據(jù)的均衡分布,卻忽略了數(shù)據(jù)間的關(guān)聯(lián)關(guān)系,導(dǎo)致大量不必要的數(shù)據(jù)傳輸任務(wù)[4].文獻(xiàn)[5-6]基于Hadoop的分布式文件系統(tǒng)HBase實(shí)現(xiàn)了對(duì)空間數(shù)據(jù)的部署管理,提升了查詢海量空間數(shù)據(jù)的效率,但不能滿足空間數(shù)據(jù)的復(fù)雜查詢；目前高性能并行GIS多采用對(duì)象關(guān)系型數(shù)據(jù)庫(kù)管理海量空間數(shù)據(jù)[7-10],文獻(xiàn)[11-12]在Oracle Spatial基于空間位置范圍劃分策略的基礎(chǔ)上,分別采用基于Hilbert空間填充曲線和K-平均聚類算法,實(shí)現(xiàn)了對(duì)原子空間數(shù)據(jù)項(xiàng)的均衡分配,但未考慮特定的多個(gè)相鄰區(qū)域空間查詢的并行效率.

在實(shí)際應(yīng)用中,通常在特定比例尺下,當(dāng)多用戶并發(fā)訪問或涉及多區(qū)域間的空間信息且這些區(qū)域集中在同一個(gè)節(jié)點(diǎn)時(shí),就會(huì)導(dǎo)致該節(jié)點(diǎn)過載,同時(shí)其他節(jié)點(diǎn)的計(jì)算資源空閑,形成對(duì)某個(gè)節(jié)點(diǎn)較長(zhǎng)時(shí)間的依賴性,影響系統(tǒng)的整體性能.因此,為提高該場(chǎng)景下的并行計(jì)算效率,本文采用基于圖著色理論的空間數(shù)據(jù)部署策略和方法,通過將空間數(shù)據(jù)粒度部署轉(zhuǎn)化為頂點(diǎn)著色模型,利用各節(jié)點(diǎn)的任務(wù)量作為約束條件對(duì)算法進(jìn)行修正,使得各節(jié)點(diǎn)數(shù)據(jù)負(fù)載達(dá)到均衡的同時(shí),相鄰空間區(qū)域盡量離散化分布,從而提高查詢的并行化程度,并以遼寧省林地?cái)?shù)據(jù)為例,驗(yàn)證了該方法的有效性.

1 基于圖著色的空間數(shù)據(jù)部署模型構(gòu)建

由于采用的并行計(jì)算策略是在進(jìn)行一次空間查詢時(shí),將任務(wù)調(diào)度至相關(guān)節(jié)點(diǎn)進(jìn)行運(yùn)算,因而系統(tǒng)的響應(yīng)時(shí)間由參與計(jì)算的節(jié)點(diǎn)數(shù)、各節(jié)點(diǎn)參與計(jì)算的數(shù)據(jù)量和節(jié)點(diǎn)之間的數(shù)據(jù)傳輸決定.

定義1系統(tǒng)響應(yīng)時(shí)間定義為

其中:T(pi)表示各節(jié)點(diǎn)處理任務(wù)的時(shí)間;Tcomm(i)表示由于數(shù)據(jù)傳輸耗費(fèi)的通訊時(shí)間;m表示節(jié)點(diǎn)數(shù)量.由式(1)可知,要提高系統(tǒng)的響應(yīng)數(shù)間,數(shù)據(jù)部署時(shí)應(yīng)使各節(jié)點(diǎn)的任務(wù)量分布均衡,以減少各節(jié)點(diǎn)處理任務(wù)的時(shí)間差異；數(shù)據(jù)部署后使各節(jié)點(diǎn)的子任務(wù)聯(lián)系盡量少,以減少數(shù)據(jù)傳輸?shù)臅r(shí)間消耗.

采用數(shù)據(jù)粒度表示空間數(shù)據(jù)對(duì)象經(jīng)一定的劃分規(guī)則得到數(shù)據(jù)表的度量,它直接影響數(shù)據(jù)表的掃描時(shí)間和數(shù)據(jù)命中率.對(duì)于空間數(shù)據(jù)粒度查詢過程,若所涉及查詢的數(shù)據(jù)粒度盡可能分布在多個(gè)節(jié)點(diǎn)上,且相鄰的數(shù)據(jù)粒度不在同一個(gè)節(jié)點(diǎn)上,則能充分利用并行資源,提高并行度,并極大降低各節(jié)點(diǎn)子任務(wù)之間的通訊.因此,基于該思想可將數(shù)據(jù)粒度的部署轉(zhuǎn)化為圖著色過程.

1.1基于圖著色的數(shù)據(jù)部署模型構(gòu)建

圖著色是指對(duì)圖的每個(gè)頂點(diǎn)(邊或面)指定一種顏色,使相鄰的頂點(diǎn)(邊或面)不同色.主要包括頂點(diǎn)著色、邊著色和圖的全著色.經(jīng)過一定的變換,圖的邊著色和全著色都可以等價(jià)轉(zhuǎn)化為圖的頂點(diǎn)著色.該問題可描述為：給定無向圖G(V,E),V={v1,v2,…,vn},建立映射C:V→{c1,c2,…,ck},使得對(duì)任意的(vi,vj)∈E,C(vi)≠C(vj).因此,本文采用頂點(diǎn)著色為V中的頂點(diǎn)進(jìn)行著色,即在滿足一定條件下,使得任意兩個(gè)相鄰頂點(diǎn)的顏色不相同[13].

在分布式存儲(chǔ)的并行體系中,任務(wù)計(jì)算和數(shù)據(jù)交換通過節(jié)點(diǎn)和網(wǎng)絡(luò)進(jìn)行,本文僅考慮同構(gòu)網(wǎng)絡(luò),即節(jié)點(diǎn)間的參數(shù)相同,用點(diǎn)集P={p1,p2,…,pm}表示m個(gè)節(jié)點(diǎn).

定義2(數(shù)據(jù)粒度分布圖) 數(shù)據(jù)粒度及其空間相鄰關(guān)系可用一個(gè)無向圖G=(V,E)表示,其中:V中的頂點(diǎn)表示數(shù)據(jù)粒度,即V={vi|待分配的所有數(shù)據(jù)粒度i};E中的邊表示數(shù)據(jù)粒度之間的空間相鄰性,即E={(vi,vj)|數(shù)據(jù)粒度的空間相鄰性}.每個(gè)頂點(diǎn)v(v∈V)有一個(gè)w表示v所表達(dá)的數(shù)據(jù)粒度大小.

定義3(數(shù)據(jù)粒度映射) 用一個(gè)映射函數(shù)表示數(shù)據(jù)粒度到計(jì)算機(jī)的映射M：V→P,如果頂點(diǎn)l(l∈V)表示的數(shù)據(jù)粒度被部署到節(jié)點(diǎn)p(p∈P)上,則M(l)=p.

定義4(頂點(diǎn)著色的數(shù)據(jù)部署模型) 設(shè)顏色集合C={c1,c2,…,cm},給定數(shù)據(jù)粒度分布圖G(V,E),V={v1,v2,…,vn},建立映射M:V→C,使得對(duì)任意的(vi,vj)∈E,C(vi)∩C(vj)=?,且C=P,則M定義的映射關(guān)系由空間拓?fù)溧徑泳仃嘐n×n確定,并有

且當(dāng)E(i,j)=1時(shí),vi與vj不可分配在同一個(gè)節(jié)點(diǎn)上.

在數(shù)據(jù)粒度部署中,節(jié)點(diǎn)對(duì)應(yīng)于顏色集合C={cm|1≤m≤M}.數(shù)據(jù)部署過程如圖1所示.

圖1 空間數(shù)據(jù)部署過程Fig.1 Spatial data placement

1.2評(píng)價(jià)指標(biāo)

2 基于圖著色模型的數(shù)據(jù)部署求解方法

本文提出的基于圖著色模型的數(shù)據(jù)部署求解方法過程分為兩個(gè)階段：Ⅰ.基于頂點(diǎn)著色算法求得任一相鄰的空間數(shù)據(jù)粒度都不在同一節(jié)點(diǎn)；Ⅱ.動(dòng)態(tài)統(tǒng)計(jì)各節(jié)點(diǎn)的任務(wù)量,并以此修正第Ⅰ階段的分配行為,確定最終的數(shù)據(jù)部署方案.

2.1數(shù)據(jù)部署求解第Ⅰ階段

對(duì)于無向圖G(V,E),頂點(diǎn)序列V={v1,v2,…,vn}(n為待分配數(shù)據(jù)粒度總數(shù)),顏色集C={c1,c2,…,cm}, 通過E(i,j)的取值判斷頂點(diǎn)間的空間位置關(guān)系,將其作為一個(gè)約束條件,以實(shí)現(xiàn)數(shù)據(jù)粒度的離散化分布,算法可描述為：

1)給v1著色,在顏色集C中選擇第1個(gè)顏色c1給v1著色,將v1移至已著色頂點(diǎn)集V(k)中,且c1標(biāo)記為已使用顏色;

2)給v2著色,判斷v2與v1的空間位置關(guān)系,如果E(1,2)=0,則用c1為v2著色；否則,從C中去除c1,選擇可著色集中的一個(gè)元素c2為v2著色,將v2移至已著色頂點(diǎn)V(k)中,且c2標(biāo)記為已使用顏色;

3)給vi(i≥3)著色,依次判斷vi與V(k)中頂點(diǎn)的空間位置關(guān)系.如果都不相鄰,則從已使用顏色中任選一種顏色ct為vi著色,否則,從C中去除相鄰頂點(diǎn)所著色的顏色,并在剩余可著顏色中選擇一種顏色cm為vi著色,將vi移至已著色的頂點(diǎn)集合中,為頂點(diǎn)vi+1著色,圖2為給頂點(diǎn)vi著色的算法流程;

4)當(dāng)V-V(k)≠?時(shí),轉(zhuǎn)3)；否則,著色完成,生成著色方案C;

5)將每種顏色ck對(duì)應(yīng)一個(gè)數(shù)據(jù)節(jié)點(diǎn)pk,找出所有著ck顏色的頂點(diǎn),即所代表的數(shù)據(jù)粒度,部署給該數(shù)據(jù)節(jié)點(diǎn)pk,直到每個(gè)數(shù)據(jù)節(jié)點(diǎn)部署完成為止.

該算法的特點(diǎn)是優(yōu)先使用已分配數(shù)據(jù)的節(jié)點(diǎn),但隨著數(shù)據(jù)粒度逐漸增多,會(huì)出現(xiàn)節(jié)點(diǎn)間數(shù)據(jù)分布不均衡的情況,將加重個(gè)別節(jié)點(diǎn)的計(jì)算負(fù)載,延長(zhǎng)系統(tǒng)總體的響應(yīng)時(shí)間.

2.2數(shù)據(jù)部署求解第Ⅱ階段

3 實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)為遼寧省2005年度林地?cái)?shù)據(jù),包含小班數(shù)據(jù)共有1 535 720條(小班在行政級(jí)別上低于村的林業(yè)管理單元).小班數(shù)據(jù)類型為面狀矢量數(shù)據(jù),共有50個(gè)屬性字段,既包括反映森林資源現(xiàn)狀和變化的屬性信息,如權(quán)屬、地類、優(yōu)勢(shì)樹種、面積等,也包括反映空間特征的信息,如空間數(shù)據(jù)類型、空間位置坐標(biāo)等.其中縣級(jí)行政單位共有124個(gè),經(jīng)實(shí)驗(yàn)分析和數(shù)據(jù)管理的綜合考慮,本文采用縣級(jí)單位作為數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)粒度單元,并經(jīng)過一定的拆分和合并,形成以縣為單位的105個(gè)數(shù)據(jù)粒度.

3.2實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)環(huán)境由4臺(tái)服務(wù)器組成服務(wù)器集群,服務(wù)器為IBM X3650M4服務(wù)器,CPU為英特至強(qiáng)E5-2609 2.4 GHz,24 GB內(nèi)存,8×600 GB硬盤.主節(jié)點(diǎn)為其中一臺(tái)的服務(wù)器,同時(shí)該4臺(tái)服務(wù)器也充當(dāng)數(shù)據(jù)節(jié)點(diǎn),每個(gè)數(shù)據(jù)節(jié)點(diǎn)由Oracle Spatial提供存儲(chǔ)支持.

3.3遼寧省縣級(jí)數(shù)據(jù)粒度部署實(shí)例

首先按空間拓?fù)潢P(guān)系生成105×105的空間關(guān)系矩陣,并采用數(shù)據(jù)部署求解第Ⅰ階段中基于頂點(diǎn)著色模型的數(shù)據(jù)粒度部署算法,結(jié)果如圖4所示；采用數(shù)據(jù)部署求解第Ⅱ階段中通過負(fù)載均衡改進(jìn)的算法生成數(shù)據(jù)分布圖,結(jié)果如圖5所示.

1,2,3,4分別表示數(shù)據(jù)節(jié)點(diǎn)1,2,3,4.

1,2,3,4分別表示數(shù)據(jù)節(jié)點(diǎn)1,2,3,4.

由圖4和圖5可見,隨著算法約束條件的增加,空間數(shù)據(jù)在各數(shù)據(jù)節(jié)點(diǎn)上的部署也隨之發(fā)生改變.分別根據(jù)圖4和圖5中統(tǒng)計(jì)數(shù)據(jù)節(jié)點(diǎn)的數(shù)據(jù)粒度分布情況,結(jié)果列于表1和表2.

表1 基于頂點(diǎn)著色模型的數(shù)據(jù)節(jié)點(diǎn)記錄數(shù)分布情況Table 1 Vertex coloring based records distribution of data nodes

表2 改進(jìn)算法的數(shù)據(jù)節(jié)點(diǎn)記錄數(shù)分布情況Table 2 Records distribution of data nodes after algorithm improvement

1,2,3,4分別表示數(shù)據(jù)節(jié)點(diǎn)1,2,3,4.

由表1可見:通過每個(gè)數(shù)據(jù)節(jié)點(diǎn)的表總數(shù)對(duì)比,發(fā)現(xiàn)4個(gè)數(shù)據(jù)節(jié)點(diǎn)的表數(shù)量分布不均衡;各數(shù)據(jù)節(jié)點(diǎn)的記錄數(shù)差別較大,存儲(chǔ)量變異系數(shù) C.V1=17.34%.由表2可見：通過每個(gè)數(shù)據(jù)節(jié)點(diǎn)的表總數(shù)對(duì)比,4個(gè)數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)的表總數(shù)非常均勻;存儲(chǔ)量變異系數(shù)C.V2=4.55%,明顯小于C.V1的值.

實(shí)驗(yàn)結(jié)果表明,通過改進(jìn)算法各數(shù)據(jù)節(jié)點(diǎn)表的數(shù)據(jù)分布更均衡,各數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)的記錄數(shù)離散程度顯著減少,使得數(shù)據(jù)負(fù)載更趨于均衡.

如圖6所示,當(dāng)進(jìn)行任意區(qū)域的空間數(shù)據(jù)查詢時(shí),數(shù)據(jù)節(jié)點(diǎn)1涉及2個(gè)數(shù)據(jù)粒度,數(shù)據(jù)節(jié)點(diǎn)2為3個(gè),數(shù)據(jù)節(jié)點(diǎn)3為3個(gè),數(shù)據(jù)節(jié)點(diǎn)4為3個(gè),這些數(shù)據(jù)粒度不僅離散地分布在4個(gè)數(shù)據(jù)節(jié)點(diǎn)上,且各節(jié)點(diǎn)的任務(wù)量趨于均衡.

綜上所述,本文描述了在并行計(jì)算環(huán)境下,面對(duì)任意空間區(qū)域的信息快速查詢,提出了一種基于圖著色理論的空間矢量數(shù)據(jù)部署方法,將數(shù)據(jù)粒度的部署轉(zhuǎn)化為基于頂點(diǎn)著色模型的圖著色過程,將數(shù)據(jù)粒度間的空間拓?fù)潢P(guān)系和數(shù)據(jù)節(jié)點(diǎn)的存儲(chǔ)量作為約束條件,修正了基于頂點(diǎn)著色模型的數(shù)據(jù)部署算法,并通過實(shí)驗(yàn)證明該方法實(shí)現(xiàn)了數(shù)據(jù)節(jié)點(diǎn)間存儲(chǔ)負(fù)載均衡,以及空間位置相鄰數(shù)據(jù)粒度的離散分布,為海量空間矢量數(shù)據(jù)在多數(shù)據(jù)節(jié)點(diǎn)上的均勻部署提供了一種思路,從而能在并行計(jì)算時(shí)更有效地利用并行計(jì)算資源,減少數(shù)據(jù)節(jié)點(diǎn)間的通信,提高了空間數(shù)據(jù)的快速響應(yīng)和并行分析效率.但本文由于在算法中將數(shù)據(jù)節(jié)點(diǎn)間的存儲(chǔ)量和空間拓?fù)潢P(guān)系同時(shí)作為約束條件,使得當(dāng)數(shù)據(jù)節(jié)點(diǎn)的個(gè)數(shù)選擇不合適時(shí),會(huì)出現(xiàn)個(gè)別數(shù)據(jù)粒度與所有數(shù)據(jù)節(jié)點(diǎn)沖突,導(dǎo)致無法分配的問題,這需要根據(jù)實(shí)際需求進(jìn)行適當(dāng)修正,以優(yōu)先保證存儲(chǔ)負(fù)載均衡.

[1] 王結(jié)臣,王豹,胡瑋,等.并行空間分析算法研究進(jìn)展及評(píng)述 [J].地理與地理信息科學(xué),2011,27(6):1-5.(WANG Jiechen,WANG Bao,HU Wei,et al.Review on Parallel Spatial Analysis Algorithms [J].Geography and Geo-Information Science,2011,27(6):1-5.)

[2] 李峙,陳朝暉.空間疊加分析中的分而治之算法研究與應(yīng)用 [J].計(jì)算機(jī)工程與應(yīng)用,2009,45(34):230-232.(LI Zhi,CHEN Chaohui.Study and Applications of Divide and Conquer Algorithm in Spatial Overlay Analysis [J].Computer Engineering and Applications,2009,45(34):230-232.)

[3] 宋杰,李甜甜,閆振興,等.數(shù)據(jù)密集型計(jì)算中負(fù)載均衡的數(shù)據(jù)布局方法 [J].北京郵電大學(xué)學(xué)報(bào),2013,36(4):76-80.(SONG Jie,LI Tiantian,YAN Zhenxing,et al.Load-Balanced Data Layout Approach in Data-Intensive Computing [J].Journal of Beijing University of Posts and Telecommunications,2013,36(4):76-80.)

[4] 王藝文,蘇森,謝琛甫,等.跨數(shù)據(jù)中心的關(guān)聯(lián)云數(shù)據(jù)部署策略 [J].華中科技大學(xué)學(xué)報(bào):自然科學(xué)版,2013,41(增刊2):48-51.(WANG Yiwen,SU Sen,XIE Chenfu,et al.Dependent Cloud Data Placement on Geo-Datacenters [J].Huazhong University of Science and Technology:Natural Science Edition,2013,41(Suppl 2):48-51.)

[5] 崔鑫.海量空間數(shù)據(jù)的分布式存儲(chǔ)管理及并行處理技術(shù)研究 [D].長(zhǎng)沙:國(guó)防科學(xué)技術(shù)大學(xué),2010.(CUI Xin.Research on Massive Spatial Data Distributed Storage and Parallel Processing Technology [D].Changsha:National University of Defense Technology,2010.)

[6] 范建永,龍明,熊偉.基于HBase的矢量空間數(shù)據(jù)分布式存儲(chǔ)研究 [J].地理與地理信息科學(xué),2012,28(5):39-42.(FAN Jianyong,LONG Ming,XIONG Wei.Research of Vector Spatial Data Distributed Storage Based on HBase [J].Geography and Geo-Information Science,2012,28(5):39-42.)

[7] 趙春宇.高性能并行GIS中矢量數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究 [D].武漢:武漢大學(xué),2006.(ZHAO Chunyu.Studying on the Technolgies of Storage and Processing of Spatial Vector Data in High-Performance Parallel GIS [D].Wuhan:Wuhan University,2006.)

[8] 宋效東,竇萬峰,湯國(guó)安,等.分布式并行地形分析中數(shù)據(jù)劃分機(jī)制研究 [J].國(guó)防科技大學(xué)學(xué)報(bào),2013,35(1):130-135.(SONG Xiaodong,DOU Wanfeng,TANG Guo’an,et al.Research on Data Partitioning of Distributed Parallel Terrain Analysis [J].Journal of National University of Defense Technology,2013,35(1):130-135.)

[9] Jean-Marie A,Lefebvre-Barbaroux S,LIU Zhen.An Analytical Approach to the Performance Evaluation of Master-Slave Computational Model [J].Parallel Computing,1998,24(5/6):841-862.

[10] SUN Xianhe,Gustafsom J L.Towards a Better Parallel Performance Metric [J].Parallel Computing,1991,17(10/11):1093-1109.

[11] 賈婷,魏祖寬,唐曙光,等.一種面向并行空間查詢的數(shù)據(jù)劃分方法 [J].計(jì)算機(jī)科學(xué),2010,37(8):198-200.(JIA Ting,WEI Zukuan,TANG Shuguang,et al.New Spatial Data Partition Approach for Spatial Data Query [J].Computer Science,2010,37(8):198-200.)[12] 趙春宇,孟令奎,林志勇.一種面向并行空間數(shù)據(jù)庫(kù)的數(shù)據(jù)劃分算法研究 [J].武漢大學(xué)學(xué)報(bào):信息科學(xué)版,2006,31(11):962-965.(ZHAO Chunyu,MENG Lingkui,LIN Zhiyong.Spatial Data Partitioning towards Parallel Spatial Database System [J].Geomatics and Information Science of Wuhan University,2006,31(11):962-965.)

[13] 朱虎,宋恩民,路志宏.求解圖著色問題的最大最小蟻群搜索算法 [J].計(jì)算機(jī)仿真,2010,27(3):190-192.(ZHU Hu,SONG Enmin,LU Zhihong.Max-Min Ant Search Algorithm for Solving Graph Coloring Problem [J].Computer Simulation,2010,27(3):190-192.)

(責(zé)任編輯：韓 嘯)

GraphColoringBasedSpatialDataPlacementtowardsParallelComputingSystem

YIN Junru1,TANG Xiaoming1,LI Xingying2,BU Xiangliang3

(1.ResearchInstituteofResourceInformationTechniques,ChineseAcademyofForestry,Beijing100091,China;2.RS,GIS,GPSTechnologyResearch&DevelopmentCenter,GuangxiForestInventory&PlanningInstitute,Nanning530011,China;3.CollegeofSoilandWaterConservation,BeijingForestryUniversity,Beijing100083,China)

An algorithm suitable for spatial vector data placement based on graph coloring theory was presented in the parallel system of computing distributed to data nodes.The deployment problem was transferred into graph vertex coloring problem,and the information query efficiency of any spatial area was thus improved.Moreover,the algorithm based on graph vertex coloring problem was proposed and improved by the task of nodes.This algorithm can achieve discrete deployment of massive spatial data granularity and storage load balance of the nodes,improve the degree of parallelism spatial data retrieval and query,and make full use of parallel computing resources.

spatial data placement;data granularity;parallel computing system;graph coloring theory;load balancing

10.13413/j.cnki.jdxblxb.2015.03.33

2014-10-28.

殷君茹(1986—),女,漢族,博士研究生,從事GIS開發(fā)與應(yīng)用的研究,E-mail:yinjr1986@163.com.通信作者：唐小明(1959—),男,漢族,博士,研究員,博士生導(dǎo)師,從事GIS開發(fā)與應(yīng)用的研究,E-mail:tangxm@caf.ac.cn.

國(guó)家高技術(shù)研究發(fā)展計(jì)劃863項(xiàng)目基金(批準(zhǔn)號(hào)：2012AA102001)和國(guó)家林業(yè)公益性行業(yè)科研專項(xiàng)基金(批準(zhǔn)號(hào)：201304215).

TP391

：A

：1671-5489(2015)03-0525-06