地籍數(shù)據(jù)庫點線拓撲一致性并行檢查方法*

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

地籍數(shù)據(jù)庫點線拓撲一致性并行檢查方法*

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

針對拓撲檢查算法復雜、計算量大，串行計算已遠不能滿足海量地籍數(shù)據(jù)高效拓撲檢查需求的問題，在分析了點線拓撲關系的并行特點基礎上，將界址點的數(shù)據(jù)劃分方法與界址線的Q＆R空間索引方法相結合，實現(xiàn)了界址點與界址線的并行拓撲計算。用某地區(qū)實際的界址點集與界址線集對點線拓撲并行檢查進行實驗。測試結果表明:并行檢查算法的并行效率隨著進程數(shù)的增加而有所衰減，但穩(wěn)定在30%以上，加速比達到5以上，且相比于ArcGIS效率提升了30倍以上。并行檢查方法以工具的方式集成應用于高性能地理計算平臺中，應用效果良好。

地籍數(shù)據(jù)庫；拓撲關系；數(shù)據(jù)質(zhì)量；并行計算；高性能地理計算平臺

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

1 拓撲關系基本原理

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

2 界址點與界址線拓撲與并行計算

2.1 界址點與界址線拓撲并行分析

界址點與界址線拓撲一致性檢查就是計算界址點是否在界址線上。界址點與界址線拓撲關系僅包含相離和包含兩種類型，其中兩者的相離關系為界址點不在界址線上，而包含關系是界址點在界址線上。地籍點線(界址點與界址線)拓撲一致性檢查過程如圖1所示，在界址點與界址線拓撲關系計算過程中先要判斷點、線的外包圍矩形(Minimum Bounding Rectangle，MBR)是否相交，若MBR為相交關系(intersects)，則在MBR相交關系的基礎上進行線包含點的拓撲關系計算，若MBR不相交，則點、線之間為相離關系。因此，界址點與界址線拓撲關系之間的計算過程［20］為:

圖1 點線拓撲關系計算過程Fig.1 Process of topology calculation of point-line

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

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

圖2 點線判斷過程Fig.2 Judgement process of point-line

據(jù)此，點線拓撲關系計算特點為:(1)點線拓撲需要高效過濾與界址點相離的界址線的方法；(2)點線拓撲關系計算中各界址點之間采用相同的計算流程完成計算(各單元之間的計算獨立、互不影響)；(3)界址點與界址線拓撲關系的計算強度與界址線所包含的頂點數(shù)相關，即界址線的頂點數(shù)可體現(xiàn)界址點與界址線拓撲計算復雜度(計算量)。

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

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

2.2 界址點與界址線拓撲并行化方法

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

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

(1)通過深度為n的Q樹對空間進行初次劃分，每次計算以各Q樹的葉子節(jié)點為一個單元；

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

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

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

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

圖3 界址點與界址線并行拓撲檢查Fig.3 Parallel topology check of boundary points and boundary lines

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

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

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

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

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

(5)重復步驟4直至所有的空間對象分配至Q樹的葉子節(jié)點；

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

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

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

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

3 實驗

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

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

3.2 測試結果

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

圖5 界址點與界址線拓撲計算結果Fig.5 Results of topology calculation of boundary points and boundary lines

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

表1 點線拓撲計算測試結果Tab.1 Result of point-line topology calculation

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

圖7 計算時間與I/O時間對比Fig.7 Rratio of computing time and I/O time

4 結論

針對地籍數(shù)據(jù)質(zhì)量檢查中界址點與界址線拓撲一致性的并行化檢查方法進行了探索與研究，并行效率達到30%以上，并行加速比達到5.23。由于測試是在千兆通信網(wǎng)的集群環(huán)境中進行的，需考慮集群I/O的時間消耗，當進程數(shù)增加時結果受I/O影響較大，界址點與界址線拓撲檢查方法的并行加速比會隨著進程數(shù)的增加而有所衰減。若在高性能網(wǎng)絡上進行測試，則無須考慮I/ O的影響。通過實驗也驗證了方法的可行性。將空間索引與空間數(shù)據(jù)劃分方法相結合的方法為地籍數(shù)據(jù)的拓撲一致性研究與探索提供了一種研究思路，為后續(xù)的界址線與宗地、宗地與宗地之間拓撲一致性的研究提供了基礎。

References)

［1］馮杭建，葉建生，許佳立.基于規(guī)則的地籍數(shù)據(jù)拓撲關系高效檢測［J］.測繪與空間地理信息，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］吳長彬，閭國年，舒飛躍.基于知識與規(guī)則的地籍數(shù)據(jù)質(zhì)量檢查方法［J］.地理與地理信息科學，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］.南寧:廣西師范學院，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ù)存取與處理關鍵技術研究［D］.武漢:武漢大學，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ù)庫拓撲關系分析及基于規(guī)則的驗證方法［J］.計算機應用，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］謝忠，葉梓，吳亮.簡單要素模型下多邊形疊置分析算法［J］.地理與地理信息科學，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］任沂斌，陳振杰，李飛雪，等.簡單要素模型多邊形拓撲檢查并行算法［J］.計算機應用，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］吳立新，楊宜舟，秦承志，等.面向新型硬件構架的新一代GIS基礎并行算法研究［J］.地理與地理科學，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］楊宜舟，吳立新，郭甲騰，等.一種實現(xiàn)拓撲關系高效并行計算的矢量數(shù)據(jù)劃分方法［J］.地理與地理信息科學，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中的方向關系［J］.解放軍測繪學院學報，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ù)庫綜合中圖斑拓撲關系的創(chuàng)建和一致性維護［J］.武漢大學學報(信息科學版)，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］白建軍，趙學勝，陳軍.基于線性四叉樹的全球離散格網(wǎng)索引［J］.武漢大學學報(信息科學版)，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］余接情，吳立新.球體坐標與SDOG-ESSG格網(wǎng)碼的相互轉(zhuǎn)換算法［J］.武漢大學學報(信息科學版)，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樹的分布式并行空間索引機制研究［J］.地理與地理信息科學，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

國家863計劃資助項目(2011AA120302)；國家自然科學基金資助項目(41001228)；中央高校基本科研業(yè)務費資助項目(N140104002)；遼寧省自然科學基金資助項目(2015020581)

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