楊宜舟，吳立新，2，郭甲騰，劉善軍(.東北大學(xué)測(cè)繪遙感與數(shù)字礦山研究所，遼寧沈陽(yáng)089；2.中國(guó)礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇徐州22008)

地籍?dāng)?shù)據(jù)庫(kù)點(diǎn)線拓?fù)湟恢滦圆⑿袡z查方法*

楊宜舟1，吳立新1，2，郭甲騰1，劉善軍1
(1.東北大學(xué)測(cè)繪遙感與數(shù)字礦山研究所，遼寧沈陽(yáng)110819；2.中國(guó)礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇徐州221008)

針對(duì)拓?fù)錂z查算法復(fù)雜、計(jì)算量大，串行計(jì)算已遠(yuǎn)不能滿足海量地籍?dāng)?shù)據(jù)高效拓?fù)錂z查需求的問(wèn)題，在分析了點(diǎn)線拓?fù)潢P(guān)系的并行特點(diǎn)基礎(chǔ)上，將界址點(diǎn)的數(shù)據(jù)劃分方法與界址線的Q＆R空間索引方法相結(jié)合，實(shí)現(xiàn)了界址點(diǎn)與界址線的并行拓?fù)溆?jì)算。用某地區(qū)實(shí)際的界址點(diǎn)集與界址線集對(duì)點(diǎn)線拓?fù)洳⑿袡z查進(jìn)行實(shí)驗(yàn)。測(cè)試結(jié)果表明:并行檢查算法的并行效率隨著進(jìn)程數(shù)的增加而有所衰減，但穩(wěn)定在30%以上，加速比達(dá)到5以上，且相比于ArcGIS效率提升了30倍以上。并行檢查方法以工具的方式集成應(yīng)用于高性能地理計(jì)算平臺(tái)中，應(yīng)用效果良好。

地籍?dāng)?shù)據(jù)庫(kù)；拓?fù)潢P(guān)系；數(shù)據(jù)質(zhì)量；并行計(jì)算；高性能地理計(jì)算平臺(tái)

地籍?dāng)?shù)據(jù)庫(kù)作為空間數(shù)據(jù)庫(kù)的一種，其涉及的土地權(quán)屬要素為:界址點(diǎn)、界址線及宗地?；谝?guī)則的拓?fù)湟恢滦詸z查是土地權(quán)屬要素質(zhì)量檢查的研究重點(diǎn)，而界址點(diǎn)與界址線之間的重合檢查屬于地籍?dāng)?shù)據(jù)拓?fù)湟恢滦詸z查中重要部分［1］。地籍?dāng)?shù)據(jù)庫(kù)的質(zhì)量控制問(wèn)題一直是國(guó)際地籍學(xué)術(shù)界和產(chǎn)業(yè)界的前沿研究領(lǐng)域，其研究?jī)?nèi)容包括空間數(shù)據(jù)位置精度、語(yǔ)義屬性精度與邏輯一致性，而其中的研究熱點(diǎn)是地籍?dāng)?shù)據(jù)的邏輯一致性，核心問(wèn)題為拓?fù)湟恢滦缘木S護(hù)問(wèn)題［2］。地籍拓?fù)湟恢滦跃S護(hù)的重要組成部分是空間拓?fù)錂z查，是拓?fù)潢P(guān)系在地籍?dāng)?shù)據(jù)質(zhì)量控制中的應(yīng)用。由于不同平臺(tái)空間拓?fù)涞囊?、空間組織與表達(dá)的差異性，特別是空間數(shù)據(jù)的采集精度、采用的技術(shù)方法不一致導(dǎo)致了地籍?dāng)?shù)據(jù)之間難以統(tǒng)一［3］。隨著國(guó)土資源“一張圖”建設(shè)全面展開(kāi)，地籍?dāng)?shù)據(jù)的數(shù)據(jù)量也日益增長(zhǎng)［4］，而且地籍?dāng)?shù)據(jù)本身的空間復(fù)雜性使傳統(tǒng)串行環(huán)境下的空間拓?fù)錂z查方法已遠(yuǎn)不能滿足實(shí)際應(yīng)用中地籍?dāng)?shù)據(jù)拓?fù)湟恢滦愿咝z查的需求。雖然近年計(jì)算機(jī)計(jì)算能力迅速提高，尤其是多核計(jì)算機(jī)和并行計(jì)算機(jī)開(kāi)始普及，但傳統(tǒng)拓?fù)錂z查的串行算法卻難以充分利用這些先進(jìn)的計(jì)算資源［5］。因此，如何充分利用這些新的計(jì)算資源來(lái)解決更復(fù)雜的實(shí)際應(yīng)用，已成為目前十分關(guān)注的問(wèn)題。在信息領(lǐng)域，并行計(jì)算為協(xié)同利用更多的計(jì)算資源提供了新的手段，實(shí)現(xiàn)了利用多個(gè)計(jì)算節(jié)點(diǎn)的計(jì)算資源來(lái)提高計(jì)算能力［6］，為高效處理大規(guī)?？臻g數(shù)據(jù)的拓?fù)潢P(guān)系檢查提供了理論和技術(shù)支撐。傳統(tǒng)的商業(yè)軟件需在建立全局拓?fù)潢P(guān)系基礎(chǔ)上，通過(guò)全局拓?fù)潢P(guān)系來(lái)查詢與目標(biāo)對(duì)象相鄰(相交)的空間對(duì)象進(jìn)行拓?fù)錂z查(快速過(guò)濾不與目標(biāo)對(duì)象相交的空間對(duì)象集)；但在大數(shù)據(jù)的環(huán)境下建立全局拓?fù)潢P(guān)系耗時(shí)較長(zhǎng)難以滿足高效拓?fù)錂z查的需求［7-9］?，F(xiàn)已有部分地理計(jì)算平臺(tái)(Geographic Information System，GIS)算法通過(guò)數(shù)據(jù)劃分基本實(shí)現(xiàn)并行計(jì)算［10］，但串行拓?fù)錂z查需要全局拓?fù)潢P(guān)系，難以通過(guò)劃分全局拓?fù)潢P(guān)系來(lái)實(shí)現(xiàn)拓?fù)錂z查的并行化［11］。特別是對(duì)于點(diǎn)線拓?fù)溆?jì)算的多圖層數(shù)據(jù)，僅利用現(xiàn)有數(shù)據(jù)劃分方法［12-15］不能有效提升拓?fù)洳⑿杏?jì)算的效率，其難點(diǎn)在于:在數(shù)據(jù)劃分的基礎(chǔ)上需實(shí)現(xiàn)目標(biāo)對(duì)象與其相鄰空間數(shù)據(jù)的高效查詢(即高效過(guò)濾與目標(biāo)對(duì)象不相交的空間對(duì)象集，而數(shù)據(jù)劃分破壞了全局拓?fù)潢P(guān)系)。楊宜舟等在分析了點(diǎn)線拓?fù)潢P(guān)系計(jì)算特點(diǎn)的基礎(chǔ)上，通過(guò)對(duì)點(diǎn)(界址點(diǎn))的單圖劃分，對(duì)線(界址線)建立空間索引，實(shí)現(xiàn)點(diǎn)線拓?fù)錂z查的并行化。同時(shí)，集成在新一代高性能GIS——高性能地理計(jì)算平臺(tái)(High Performance GIS，HiGIS)中。

1 拓?fù)潢P(guān)系基本原理

目前，空間拓?fù)潢P(guān)系的計(jì)算模型有基于點(diǎn)集理論的描述模型(4交模型［16］與9交模型［17］)、基于區(qū)域連接演算(Region Connection Calculus，RCC)理論的描述模型［18］、基于Voronoi圖的9交模型［19］等。基于點(diǎn)集理論的9交模型是當(dāng)前最為常用的拓?fù)潢P(guān)系分析和計(jì)算模型，具有廣泛的適用范圍和較高的計(jì)算效率，相比其他兩種描述模型更適合于高性能拓?fù)潢P(guān)系的計(jì)算。在目前商業(yè)軟件中，主要是使用9交模型計(jì)算目標(biāo)間的拓?fù)潢P(guān)系，最具代表性的Oracle和ArcGIS均采用基于點(diǎn)集理論維度擴(kuò)展的9交模型，分別實(shí)現(xiàn)空間關(guān)系的查詢和GIS拓?fù)浞治龅墓δ堋２捎瞄_(kāi)放地理信息系統(tǒng)協(xié)會(huì)(Open GISConsortium，OGC)基于點(diǎn)集理論維度擴(kuò)展的9交模型(Dimensionally Extended Nine-Intersection Model，DE-9IM)作為描述簡(jiǎn)單要素間拓?fù)潢P(guān)系的模型。根據(jù)這8種拓?fù)潢P(guān)系之間的聯(lián)系，可確定一個(gè)最小覆蓋關(guān)系集。該最小拓?fù)潢P(guān)系集中包含5種關(guān)系類(lèi)型:相離(disjoints)、相接(touches)、疊加(overlaps)、包含(within/contains)和穿越(crosses)。這5種關(guān)系能對(duì)所有的空間關(guān)系構(gòu)成一個(gè)完整的覆蓋，它們是基本的、互斥的。因?yàn)樵邳c(diǎn)線拓?fù)潢P(guān)系中僅有相離、包含兩種關(guān)系，所以僅針對(duì)這兩種關(guān)系進(jìn)行研究。

2 界址點(diǎn)與界址線拓?fù)渑c并行計(jì)算

2.1 界址點(diǎn)與界址線拓?fù)洳⑿蟹治?/p>

界址點(diǎn)與界址線拓?fù)湟恢滦詸z查就是計(jì)算界址點(diǎn)是否在界址線上。界址點(diǎn)與界址線拓?fù)潢P(guān)系僅包含相離和包含兩種類(lèi)型，其中兩者的相離關(guān)系為界址點(diǎn)不在界址線上，而包含關(guān)系是界址點(diǎn)在界址線上。地籍點(diǎn)線(界址點(diǎn)與界址線)拓?fù)湟恢滦詸z查過(guò)程如圖1所示，在界址點(diǎn)與界址線拓?fù)潢P(guān)系計(jì)算過(guò)程中先要判斷點(diǎn)、線的外包圍矩形(Minimum Bounding Rectangle，MBR)是否相交，若MBR為相交關(guān)系(intersects)，則在MBR相交關(guān)系的基礎(chǔ)上進(jìn)行線包含點(diǎn)的拓?fù)潢P(guān)系計(jì)算，若MBR不相交，則點(diǎn)、線之間為相離關(guān)系。因此，界址點(diǎn)與界址線拓?fù)潢P(guān)系之間的計(jì)算過(guò)程［20］為:

圖1 點(diǎn)線拓?fù)潢P(guān)系計(jì)算過(guò)程Fig.1 Process of topology calculation of point-line

(1)界址點(diǎn)p與界址線集S進(jìn)行相交檢查，獲取與界址點(diǎn)MBR相交的界址線集L={l1，l2，…，ln}。界址點(diǎn)與界址線之間先通過(guò)MBR之間相交計(jì)算，過(guò)濾掉大部分與目標(biāo)界址點(diǎn)MBR相離的界址線。在數(shù)據(jù)過(guò)濾的過(guò)程中，若采用MBR直接過(guò)濾方法(遍歷過(guò)濾)，在大數(shù)據(jù)環(huán)境下過(guò)濾過(guò)程的耗時(shí)將急劇增加(設(shè)界址點(diǎn)數(shù)為n，界址線數(shù)為m，各界址點(diǎn)都需通過(guò)遍歷m次過(guò)濾相離的界址線，那么n個(gè)界址點(diǎn)則需要遍歷n×m次，所以數(shù)據(jù)規(guī)模越大過(guò)濾所消耗的時(shí)間越長(zhǎng))，嚴(yán)重制約著界址點(diǎn)與界址線拓?fù)溆?jì)算的效率，所以在界址點(diǎn)與界址線拓?fù)潢P(guān)系并行計(jì)算中需要提供一種通過(guò)MBR快速過(guò)濾大部分相離目標(biāo)的方法。

(2)根據(jù)九交模型計(jì)算p與L中各界址線的拓?fù)潢P(guān)系結(jié)果為t(li)，若t(li)為拓?fù)浒P(guān)系，則界址點(diǎn)在界址線上，否則界址點(diǎn)不在界址線上。將界址點(diǎn)與界址線上每條線段進(jìn)行計(jì)算，判斷界址點(diǎn)是否在界址線上。點(diǎn)線判斷算法如圖2所示:點(diǎn)Q與線段兩個(gè)端點(diǎn)P1和P2構(gòu)成的向量間叉積為零，且點(diǎn)Q在線段所構(gòu)成MBR內(nèi)，則點(diǎn)Q在線段上，否則點(diǎn)在線段外。另外，對(duì)于點(diǎn)與線段兩個(gè)端點(diǎn)重合的情況，則只需要判斷點(diǎn)Q分別與P1和P2是否相等即可。由于與各界址點(diǎn)進(jìn)行拓?fù)溆?jì)算的界址線所包含的線段數(shù)目不同，則各界址點(diǎn)的計(jì)算量有所不同，即各界址點(diǎn)的計(jì)算量與界址線所包含的線段數(shù)目相關(guān)。界址線是由多個(gè)頂點(diǎn)組成，所以界址點(diǎn)與界址線拓?fù)涞挠?jì)算量與界址線所包含的頂點(diǎn)數(shù)目正相關(guān)。

圖2 點(diǎn)線判斷過(guò)程Fig.2 Judgement process of point-line

據(jù)此，點(diǎn)線拓?fù)潢P(guān)系計(jì)算特點(diǎn)為:(1)點(diǎn)線拓?fù)湫枰咝н^(guò)濾與界址點(diǎn)相離的界址線的方法；(2)點(diǎn)線拓?fù)潢P(guān)系計(jì)算中各界址點(diǎn)之間采用相同的計(jì)算流程完成計(jì)算(各單元之間的計(jì)算獨(dú)立、互不影響)；(3)界址點(diǎn)與界址線拓?fù)潢P(guān)系的計(jì)算強(qiáng)度與界址線所包含的頂點(diǎn)數(shù)相關(guān)，即界址線的頂點(diǎn)數(shù)可體現(xiàn)界址點(diǎn)與界址線拓?fù)溆?jì)算復(fù)雜度(計(jì)算量)。

根據(jù)點(diǎn)線拓?fù)潢P(guān)系計(jì)算特點(diǎn)1可知:現(xiàn)有空間數(shù)據(jù)過(guò)濾方法中最常用的是空間索引，所以需對(duì)參與計(jì)算的界址線建立空間索引，以提高界址線的過(guò)濾效率。根據(jù)點(diǎn)線拓?fù)潢P(guān)系計(jì)算特點(diǎn)2可知:將各界址點(diǎn)的計(jì)算作為子問(wèn)題，各子問(wèn)題之間的計(jì)算相互獨(dú)立，即各進(jìn)程間不需要進(jìn)行通信和等待，對(duì)界址點(diǎn)直接進(jìn)行劃分即可實(shí)現(xiàn)點(diǎn)線拓?fù)溆?jì)算的并行化。因此，根據(jù)界址點(diǎn)與界址線拓?fù)溆?jì)算特點(diǎn)1與特點(diǎn)2，通過(guò)對(duì)點(diǎn)數(shù)據(jù)的空間劃分、對(duì)線數(shù)據(jù)建立空間索引即可實(shí)現(xiàn)點(diǎn)線拓?fù)溆?jì)算的并行化。根據(jù)界址點(diǎn)與界址線拓?fù)潢P(guān)系計(jì)算的特點(diǎn)3可知:界址點(diǎn)與界址線拓?fù)溆?jì)算量的大小與界址線本身復(fù)雜度相關(guān)，即界址線包含的頂點(diǎn)數(shù)可反映點(diǎn)線拓?fù)溆?jì)算的復(fù)雜程度，通過(guò)簡(jiǎn)單的界址點(diǎn)數(shù)據(jù)劃分，并不能實(shí)現(xiàn)各進(jìn)程界址點(diǎn)子集所對(duì)應(yīng)的相交線集的頂點(diǎn)數(shù)均衡(任務(wù)均衡)的目的。因此，研究一種適合于界址點(diǎn)與界址線拓?fù)溆?jì)算并行化的方法重點(diǎn)在于界址點(diǎn)集劃分方法與界址線集的空間索引方法。

現(xiàn)有并行編程模型可分為3類(lèi)［6］:消息傳遞模型、共享存儲(chǔ)模型和數(shù)據(jù)并行模型。消息傳遞模型是目前使用最為廣泛的并行模型，其有兩大優(yōu)勢(shì):(1)消息傳遞程序具有高度的可移植性，理論上可在任何并行機(jī)上執(zhí)行，即不需要特殊的硬件支持；(2)允許用戶顯式地控制并行程序中每個(gè)進(jìn)程內(nèi)存的使用，為編程人員實(shí)現(xiàn)高性能計(jì)算提供便利。其并行程序開(kāi)發(fā)模式通常有兩種:單程序多數(shù)據(jù)［6］(Single Program Multiple Data，SPMD)模式和多程序多數(shù)據(jù)［6］(Multiple Program Multiple Data，MPMD)模式。因此，采用SPMD模式設(shè)計(jì)并行算法，根據(jù)界址點(diǎn)與界址線拓?fù)溆?jì)算特點(diǎn)，通過(guò)界址點(diǎn)集的數(shù)據(jù)劃分與界址線集的空間索引即可實(shí)現(xiàn)界址點(diǎn)與界址線拓?fù)溆?jì)算的并行化。

2.2 界址點(diǎn)與界址線拓?fù)洳⑿谢椒?/p>

根據(jù)以上并行化特點(diǎn)分析，界址點(diǎn)與界址線拓?fù)錂z查的數(shù)據(jù)分為界址點(diǎn)、界址線兩部分，在實(shí)現(xiàn)點(diǎn)線拓?fù)潢P(guān)系并行計(jì)算時(shí)兩部分?jǐn)?shù)據(jù)需分別處理，即對(duì)界址點(diǎn)集進(jìn)行劃分，對(duì)界址線集建立空間索引。界址點(diǎn)與界址線的拓?fù)錂z查的并行化方法如圖3所示，首先，對(duì)界址點(diǎn)數(shù)據(jù)進(jìn)行劃分，將空間相鄰的界址點(diǎn)劃分至不同的計(jì)算節(jié)點(diǎn)；其次，對(duì)界址線建立Q＆R索引，實(shí)現(xiàn)各計(jì)算節(jié)點(diǎn)中界址點(diǎn)對(duì)MBR相交的界址線的快速查詢；最后，各計(jì)算節(jié)點(diǎn)采用DE-9IM模型實(shí)現(xiàn)界址點(diǎn)與界址線的拓?fù)溆?jì)算。

設(shè)界址點(diǎn)集為P={p1，p2，…，pn}，界址線集為L(zhǎng)={l1，l2，…，lm}，界址點(diǎn)與各界址線之間計(jì)算量可表達(dá)為f(lj)(根據(jù)2.1節(jié)可知界址點(diǎn)與界址線的拓?fù)溆?jì)算量大小與界址線所包含的頂點(diǎn)數(shù)正相關(guān))，界址點(diǎn)影響域?yàn)閦(pi)(即與界址點(diǎn)MBR相交的所有界址線)，界址點(diǎn)影響域內(nèi)的計(jì)算量為f(pi，z(pi))，那么界址點(diǎn)集與界址線集的計(jì)算總量可表示為Σf(pi，z(pi))。界址線lj與其影響域z(li)中的g個(gè)界址點(diǎn)Si{pa，pb，…，px}進(jìn)行計(jì)算(g個(gè)界址點(diǎn)具有空間鄰近性)，其計(jì)算量可分解為g個(gè)f(lj)(Si中各點(diǎn)計(jì)算量相等，且Si中各點(diǎn)空間位置鄰近)，所以在界址點(diǎn)與界址線拓?fù)溆?jì)算中空間臨近的界址點(diǎn)的影響域z(pi)基本一致，即空間鄰近的界址點(diǎn)(pi，pi+1為相鄰的界址點(diǎn))的計(jì)算量基本相等(f(pi，z(pi))≈f(pi+1，z(pi+1)))。因此，在劃分界址點(diǎn)集時(shí)需將空間臨近的界址點(diǎn)劃分至不同的進(jìn)程進(jìn)行計(jì)算，且海量的界址點(diǎn)與界址線進(jìn)行拓?fù)溆?jì)算時(shí)不能將全部數(shù)據(jù)讀入內(nèi)存(占用過(guò)多的計(jì)算資源)，應(yīng)以分塊方式計(jì)算。具體的步驟如下:

(1)通過(guò)深度為n的Q樹(shù)對(duì)空間進(jìn)行初次劃分，每次計(jì)算以各Q樹(shù)的葉子節(jié)點(diǎn)為一個(gè)單元；

(2)由于Hilbert值排序最能反映空間臨近性，所以各進(jìn)程分別對(duì)各Q樹(shù)葉子節(jié)點(diǎn)中所包含的界址點(diǎn)進(jìn)行Hilbert空間編碼；

(3)利用并行空間排序算法對(duì)Hilbert空間編碼進(jìn)行排序；

(4)對(duì)各葉子節(jié)點(diǎn)中排序在后的界址點(diǎn)輪轉(zhuǎn)地分配至各個(gè)進(jìn)程；

(5)重復(fù)2～4步直至Q樹(shù)所有葉子節(jié)點(diǎn)中的界址點(diǎn)分配完畢。

圖3 界址點(diǎn)與界址線并行拓?fù)錂z查Fig.3 Parallel topology check of boundary points and boundary lines

界址點(diǎn)集采用Q劃分與Hilbert劃分結(jié)合的數(shù)據(jù)劃分方法，將數(shù)據(jù)集分配至各計(jì)算節(jié)點(diǎn)(通過(guò)Q樹(shù)劃分使界址點(diǎn)數(shù)據(jù)分塊，而Hilbert劃分將空間相鄰的界址點(diǎn)劃分至不同的計(jì)算節(jié)點(diǎn))。而界址線集則采用全冗余的策略，為避免在計(jì)算過(guò)程中占用過(guò)多的計(jì)算資源，也需要對(duì)界址線數(shù)據(jù)進(jìn)行分塊，并且需對(duì)界址線數(shù)據(jù)建立空間索引以滿足拓?fù)溆?jì)算過(guò)程中高效過(guò)濾的需求。因此，采用Q＆R混合索引實(shí)現(xiàn)界址線的分塊索引(如圖4所示)，具體步驟如下:

(1)計(jì)算空間對(duì)象集S中所有空間對(duì)象的最小包圍盒rn，最小包圍盒中心點(diǎn)cn；

(2)根據(jù)硬件的計(jì)算能力及空間對(duì)象集S的數(shù)目N，計(jì)算Q樹(shù)葉子節(jié)點(diǎn)的平均容量ca和Q樹(shù)的深度n；

(3)創(chuàng)建深度為n的Q樹(shù)，并按照編碼規(guī)則eC(可為任意有規(guī)律的編碼規(guī)則，如Hilbert編碼、Z曲線編碼等)對(duì)所有的葉子節(jié)點(diǎn)進(jìn)行編碼，各葉子節(jié)點(diǎn)的編碼為Cm(利用編碼規(guī)則可擴(kuò)展到全球尺度空間索引［21-22］)；

(4)根據(jù)編碼規(guī)則eC對(duì)空間對(duì)象的中心點(diǎn)cn進(jìn)行編碼，并將該空間對(duì)象分配至與其編碼相同的葉子節(jié)點(diǎn)(可快速定位Q樹(shù)葉子節(jié)點(diǎn)，避免Q樹(shù)根節(jié)點(diǎn)成為訪問(wèn)熱點(diǎn)［23］)；

(5)重復(fù)步驟4直至所有的空間對(duì)象分配至Q樹(shù)的葉子節(jié)點(diǎn)；

(6)各Q樹(shù)葉子節(jié)點(diǎn)下的數(shù)據(jù)建立R樹(shù)索引。

圖4 Q＆R空間索引Fig.4 Q tree and R treemixed spatial index

上述過(guò)程中界址點(diǎn)的Q樹(shù)劃分與Q＆R混合空間索引采用的Q樹(shù)是同一Q樹(shù)，可使界址點(diǎn)的分塊與界址線的分塊相互對(duì)應(yīng)。Q＆R混合空間索引中的Q樹(shù)不僅有數(shù)據(jù)劃分功能且具有空間索引的功能，實(shí)現(xiàn)了對(duì)R樹(shù)集的索引，而Q＆R混合空間索引中R樹(shù)集是實(shí)現(xiàn)界址線的檢索(Q＆R混合空間索引屬于雙層空間索引)。Q＆R混合空間索引的平均時(shí)間復(fù)雜度O(log(n)+log(N/4n))(N為界址線數(shù)目，n為Q樹(shù)深度)，優(yōu)于時(shí)間復(fù)雜度為O(log(N))的R樹(shù)空間索引。

設(shè)各進(jìn)程已分配的界址點(diǎn)集為Pi={q1，q2，…，qn×n}，qj為Q樹(shù)各葉子節(jié)點(diǎn)所包含的界址點(diǎn)子集，其中:0＜i≤p，0＜j≤n×n，p為進(jìn)程總數(shù)，n為Q樹(shù)深度。界址線集的Q＆R混合空間索引中Q樹(shù)葉子節(jié)點(diǎn)對(duì)應(yīng)的R樹(shù)集為M={r1，r2，…，rn×n}，rj為界址線子集空間索引，其中:0＜j≤n× n，n為Q樹(shù)深度。首先各進(jìn)程中參與計(jì)算的界址點(diǎn)集qi通過(guò)MBR(或者利用qi對(duì)應(yīng)Q樹(shù)葉子節(jié)點(diǎn)的編碼)檢索其在界址線集Q＆R空間索引中的影響區(qū)域z(例如q1珋z(r1)，z(r1)為q1在界址線集中的影響域，通過(guò)z(r1)所在的R樹(shù)查詢MBR與q1中各界址點(diǎn)相交的界址線集)，然后將qj中各界址點(diǎn)與z(rj)中檢索的界址線集進(jìn)行拓?fù)溆?jì)算(如圖3所示)，直到所有的界址點(diǎn)計(jì)算完畢。

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

3.1 測(cè)試環(huán)境與測(cè)試數(shù)據(jù)

為測(cè)試該方法的計(jì)算效率，搭建了一個(gè)小型集群的測(cè)試環(huán)境。該環(huán)境由4個(gè)高性能計(jì)算節(jié)點(diǎn)及1個(gè)存儲(chǔ)節(jié)點(diǎn)(2T)構(gòu)成，集群中各節(jié)點(diǎn)的操作系統(tǒng)是Redhat5.04(64位)，消息傳遞采用MPICH2的并行庫(kù)。本案例為對(duì)某地區(qū)界址點(diǎn)與界址線的數(shù)據(jù)質(zhì)量進(jìn)行檢查，本實(shí)驗(yàn)取某地區(qū)的174 327條界址線和1 668 276個(gè)界址點(diǎn)。

3.2 測(cè)試結(jié)果

本文方法并行拓?fù)溆?jì)算結(jié)果與在相同環(huán)境下采用ArcGIS拓?fù)溆?jì)算的結(jié)果一致，圖5為兩種方法的計(jì)算結(jié)果，其結(jié)果完全一致，圖形完全重合，圖5中五角星為點(diǎn)線拓?fù)洳灰恢碌慕Y(jié)果。ArcGIS耗時(shí)約為15min，而本文方法在16進(jìn)程下僅需26.87s即可完成計(jì)算，效率相比于串行的ArcGIS提升了30倍以上，而且本文方法也已集成應(yīng)用在HiGIS平臺(tái)中。由界址點(diǎn)與界址線拓?fù)潢P(guān)系并行計(jì)算加速比、并行效率(如圖6所示)與進(jìn)程數(shù)的統(tǒng)計(jì)關(guān)系(見(jiàn)表1)可見(jiàn):本文方法的并行效率與進(jìn)程數(shù)相關(guān)，即并行算法效率隨著進(jìn)程數(shù)增加而衰減，在16進(jìn)程下的并行效率仍穩(wěn)定在30%以上；加速比隨進(jìn)程數(shù)增加而增長(zhǎng)，在16進(jìn)程時(shí)達(dá)5.23。

圖5 界址點(diǎn)與界址線拓?fù)溆?jì)算結(jié)果Fig.5 Results of topology calculation of boundary points and boundary lines

圖6 并行效率與并行加速比Fig.6 Parallel efficiency and speedup of parallel topology calculation

表1 點(diǎn)線拓?fù)溆?jì)算測(cè)試結(jié)果Tab.1 Result of point-line topology calculation

由于測(cè)試數(shù)據(jù)受通信網(wǎng)絡(luò)和地籍?dāng)?shù)據(jù)規(guī)模的影響，并行效率會(huì)隨著進(jìn)程數(shù)目的增加而逐漸衰減，加速比會(huì)隨著進(jìn)程數(shù)目的增加而趨于穩(wěn)定。隨著進(jìn)程數(shù)目的增加，I/O(本文的I/O包含了數(shù)據(jù)劃分時(shí)間與創(chuàng)建空間索引時(shí)間)的性能會(huì)成為影響并行算法解算的性能瓶頸。如圖7所示，隨著進(jìn)程數(shù)的增加，各進(jìn)程的計(jì)算任務(wù)量會(huì)逐漸減少，而I/O耗時(shí)比率會(huì)逐漸增加，若在更大規(guī)模的界址點(diǎn)與界址線數(shù)據(jù)下，本文的方法的效率將會(huì)有進(jìn)一步的提升。

圖7 計(jì)算時(shí)間與I/O時(shí)間對(duì)比Fig.7 Rratio of computing time and I/O time

4 結(jié)論

針對(duì)地籍?dāng)?shù)據(jù)質(zhì)量檢查中界址點(diǎn)與界址線拓?fù)湟恢滦缘牟⑿谢瘷z查方法進(jìn)行了探索與研究，并行效率達(dá)到30%以上，并行加速比達(dá)到5.23。由于測(cè)試是在千兆通信網(wǎng)的集群環(huán)境中進(jìn)行的，需考慮集群I/O的時(shí)間消耗，當(dāng)進(jìn)程數(shù)增加時(shí)結(jié)果受I/O影響較大，界址點(diǎn)與界址線拓?fù)錂z查方法的并行加速比會(huì)隨著進(jìn)程數(shù)的增加而有所衰減。若在高性能網(wǎng)絡(luò)上進(jìn)行測(cè)試，則無(wú)須考慮I/ O的影響。通過(guò)實(shí)驗(yàn)也驗(yàn)證了方法的可行性。將空間索引與空間數(shù)據(jù)劃分方法相結(jié)合的方法為地籍?dāng)?shù)據(jù)的拓?fù)湟恢滦匝芯颗c探索提供了一種研究思路，為后續(xù)的界址線與宗地、宗地與宗地之間拓?fù)湟恢滦缘难芯刻峁┝嘶A(chǔ)。

References)

［1］馮杭建，葉建生，許佳立.基于規(guī)則的地籍?dāng)?shù)據(jù)拓?fù)潢P(guān)系高效檢測(cè)［J］.測(cè)繪與空間地理信息，2007，30(1):87-90.FENG Hangjian，YE Jiansheng，XU Jiali.Highly effective testing on topology relationship of cadastre data based on rule［J］.Geomatics＆Spatial Information Technology，2007，30(1):87-90.(in Chinese)

［2］周曉光，陳軍.地籍信息系統(tǒng)綜述［J］.地理信息世界，2006，4(3):35-40.ZHOU Xiaoguang，CHEN Jun.A survey on cadastral information system［J］.GeomaticsWorld，2006，4(3):35-40.(in Chinese)

［3］吳長(zhǎng)彬，閭國(guó)年，舒飛躍.基于知識(shí)與規(guī)則的地籍?dāng)?shù)據(jù)質(zhì)量檢查方法［J］.地理與地理信息科學(xué)，2007，23(5): 22-25.WU Changbin，LYU Guonian，SHU Feiyue.Research on quality checking method based on knowledge and rule to cadastral data［J］.Geography and Geo-Information Science，2007，23(5):22-25.(in Chinese)

［4］杜波.基于“一張圖”思想的城鄉(xiāng)一體化地籍管理信息系統(tǒng)研究［D］.南寧:廣西師范學(xué)院，2010.DU Bo.The research on urban-rural-integrated cadastral management information systems based on“amap”thought［D］.Nanning:Guangxi Normal University，2010.(in Chinese)

［5］趙春宇.高性能并行GIS中矢量空間數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究［D］.武漢:武漢大學(xué)，2006.ZHAO Chunyu.Studying on the technologies of storage and processing of spatial vector data in high-performance parallel GIS［D］.Wuhan:Wuhan University，2006.(in Chinese)

［6］Xavier C，Iyengar S S.Introduction to parallel algorithms［M］.USA:Wiley-Interscience，1998.

［7］馮杭建，麻土華，劉偉宏，等.地籍空間數(shù)據(jù)庫(kù)拓?fù)潢P(guān)系分析及基于規(guī)則的驗(yàn)證方法［J］.計(jì)算機(jī)應(yīng)用，2006，26(17):2522-2524.FENG Hangjian，MA Tuhua，LIUWeihong，et al.Topology relationship analysis of cadastral spatial database and validity method based on rule［J］.Journal of Computer Applications，2006，26(17):2522-2524.(in Chinese)

［8］謝忠，葉梓，吳亮.簡(jiǎn)單要素模型下多邊形疊置分析算法［J］.地理與地理信息科學(xué)，2007，23(3):19-23.XIE Zhong，YE Zi，WU Liang.Polygon overlay analysis algorithm using the simple data model［J］.Geography and Geo-Information Science，2007，23(3):19-23.(in Chinese)

［9］任沂斌，陳振杰，李飛雪，等.簡(jiǎn)單要素模型多邊形拓?fù)錂z查并行算法［J］.計(jì)算機(jī)應(yīng)用，2014，34(7):1852-1856.REN Yibin，CHEN Zhenjie，LI Feixue，et al.Parallel algorithm of polygon topology validation for simple feature model［J］.Journal of Computer Applications，2014，34(7): 1852-1856.(in Chinese)

［10］吳立新，楊宜舟，秦承志，等.面向新型硬件構(gòu)架的新一代GIS基礎(chǔ)并行算法研究［J］.地理與地理科學(xué)，2013，29(4):1-8.WU Lixin，YANG Yizhou，QIN Chengzhi，et al.On basic geographic algorithms of new generation GIS for new hardware architectures［J］.Geography and Geo-Information Science，2013，29(4):1-8.(in Chinese)

［11］Healey R，Dowers S，Gittings B，et al.Parallel processing algorithms for GIS［M］.USA:CRC Press，1998.

［12］Liu CW，Chen H.A hash partition strategy for distributed query processing［C］//Proceedings of the 5th International Conference on Extending Database Technology，Avignon，F(xiàn)rance，1996，1057:371-387.

［13］Ghandeharizadeh S，DeWitt D J.Hybrid-range partitioning strategy:a new declustering strategy for multiprocessor databases machines［C］//Proceedings of the Sixteenth International Conference on Very Large Databases，Brisbane，Australia，1990:481-492.

［14］Zhou Y，Jiang L.Hilbert curve based spatial data declustering method for parallel spatial database［C］// Proceedings of the 2nd International Conference on Remote Sensing＆Environment and Transportation Engineering，Nanjing，China，2012:1-4.

［15］楊宜舟，吳立新，郭甲騰，等.一種實(shí)現(xiàn)拓?fù)潢P(guān)系高效并行計(jì)算的矢量數(shù)據(jù)劃分方法［J］.地理與地理信息科學(xué)，2013，29(4):25-29.YANG Yizhou，WU Lixin，GUO Jiateng，et al.A method of spatial data partition for efficient parallel computing of topological relations［J］.Geography and Geo-InformationScience，2013，29(4):25-29.(in Chinese)

［16］Enghofer M J，F(xiàn)ranzosa R D.Point-set topological spatial relations［J］.International Journal of Geographical Information Systems，1991，5(2):161-174.

［17］Enghofer M J，Herring J R.Categorizing binary topological relations between regions，lines，and points in geographic databases［R］.Technical Report，University of Maine，1991.

［18］李成名，朱英浩，陳軍.利用Voronoi圖形式化描述和判斷GIS中的方向關(guān)系［J］.解放軍測(cè)繪學(xué)院學(xué)報(bào)，1998，19(2):117-120.LI Chengming，ZHU Yinghao，CHEN Jun.Directional relation description and determination based on Voronoi diagram in GIS［J］.Journal of the PLA Institute of Surveying and Mapping，1998，19(2):117-120.(in Chinese)

［19］Randell D A，Cui Z，Cohn A G.A spatial logical based on regions and connection［C］//Proceedings of 3rd International Conference on Knowledge Representation and Reasoning，New York，1992:165-176.

［20］陳先偉，郭仁忠，閆浩文.土地利用數(shù)據(jù)庫(kù)綜合中圖斑拓?fù)潢P(guān)系的創(chuàng)建和一致性維護(hù)［J］.武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2005，30(4):370-373.CHEN Xianwei，GUO Renzhong，YAN Haowen.Creation and consistency maintenance of topological relationships between patches in landuse database generalization［J］.Geomatics and Information Science of Wuhan University，2005，30(4):370-373.(in Chinese)

［21］白建軍，趙學(xué)勝，陳軍.基于線性四叉樹(shù)的全球離散格網(wǎng)索引［J］.武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2005，30(9): 805-808.BAI Jianjun，ZHAO Xuesheng，CHEN Jun.Indexing of discrete global grids using linear quadtree［J］.Geomatics and Information Science of Wuhan University，2005，30(9): 805-808.(in Chinese)

［22］余接情，吳立新.球體坐標(biāo)與SDOG-ESSG格網(wǎng)碼的相互轉(zhuǎn)換算法［J］.武漢大學(xué)學(xué)報(bào)(信息科學(xué)版)，2015，30(8):1116-1121.YU Jieqing，WU Lixin.Transformation algorithms between spheroid coordinates system and SDOG-ESSG grid code［J］.Geomatics and Information Science of Wuhan University，2015，30(8):1116-1121.(in Chinese)

［23］趙園春，李成名，趙春宇.基于R樹(shù)的分布式并行空間索引機(jī)制研究［J］.地理與地理信息科學(xué)，2007，23(6): 38-41.ZHAO Yuanchun，LIChengming，ZHAO Chunyu.Research on the distributed parallel spatial indexing schema based on R-Tree［J］.Geography and Geo-Information Science，2007，23(6):38-41.(in Chinese)

Parallel checking method for point-line topological consistency in cadastral database

YANGYizhou1，WU Lixin1，2，GUO Jiateng1，LIU Shanjun1
(1.Institute of Geo-informatics＆Digital Mine，Northeastern University，Shenyang 110819，China；2.IoT/Perception Mine Research Center，China University of Mining＆Technology，Xuzhou 221008，China)

The current topology inspection methods which use serial computation method accompanied with the complicated algorithms and excessive calculation amount cannot satisfy the demands of the efficient topology inspection for massive cadastral data.On the basis of the characteristics of topology calculation between point and line，the parallel topological computingmethod aiming at boundary points and lines has been implemented by combining the decomposition method for boundary points data with the Q tree and R tree spatial indexmethod for boundary lines data.The topology parallel testsusing the datasets of boundary points and lines in one areawas taken in thismethod.The results show that the parallel efficiency of the algorithm which decreased with the increased number of processes steady maintains at above 30%，and the parallel speedup ratio reaches up to 5.The computation efficiency is improved more than 30 times than that of ArcGIS.Themethod can be used as a tool in high performance geographic information system and achieves good application effect.

cadastral database；topological relations；data quality；parallel computing；high performance geographic information system

P273

A

1001-2486(2015)05-040-07

10.11887/j.cn.201505007

http://journal.nudt.edu.cn

2015-06-29

國(guó)家863計(jì)劃資助項(xiàng)目(2011AA120302)；國(guó)家自然科學(xué)基金資助項(xiàng)目(41001228)；中央高校基本科研業(yè)務(wù)費(fèi)資助項(xiàng)目(N140104002)；遼寧省自然科學(xué)基金資助項(xiàng)目(2015020581)

楊宜舟(1987—)，男，湖北荊門(mén)人，博士研究生，E-mail:yangyizhou1987@163.com；吳立新(通信作者)，男，教授，博士，博士生導(dǎo)師，E-mail:awulixin@263.net