唐志賢，馮 鈞，徐 曦，史涯晴,2

(1. 河海大學(xué)計算機與信息學(xué)院 南京 211110；2. 中國人民解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院 南京 210007)

面向水系河網(wǎng)的建模與索引方法研究

唐志賢1，馮 鈞1，徐 曦1，史涯晴1,2

(1. 河海大學(xué)計算機與信息學(xué)院 南京 211110；2. 中國人民解放軍理工大學(xué)指揮信息系統(tǒng)學(xué)院 南京 210007)

針對水系河網(wǎng)的非歐時空特征限制了數(shù)據(jù)查詢效率，提出了一種面向水系河網(wǎng)的建模與索引方法。該方法首先建立水系河網(wǎng)的多尺度圖論化模型，在此基礎(chǔ)上定義河段的概念，并建立基于河段的流域水系河網(wǎng)索引(BRR-Tree)實現(xiàn)水利領(lǐng)域特征的表達，用以實現(xiàn)水利領(lǐng)域語義查詢請求的表達；然后設(shè)計基于BRR-Tree的水系河網(wǎng)查詢算法，并按照水系河網(wǎng)進行數(shù)據(jù)訪問需求轉(zhuǎn)換為歐氏空間訪問需求。實驗表明該方法能夠有效地支持水系河網(wǎng)分析，提高水利領(lǐng)域數(shù)據(jù)的訪問效率。

索引; 建模; 河網(wǎng); 河段

水利行業(yè)長期的業(yè)務(wù)實踐積累了大量分布異構(gòu)獨立的業(yè)務(wù)數(shù)據(jù)[1]，隨著以物聯(lián)網(wǎng)、云計算、移動互聯(lián)網(wǎng)和RS技術(shù)為基礎(chǔ)的智慧水利規(guī)劃的實施，逐步形成天地一體的水利監(jiān)測體系[1]，將帶來數(shù)據(jù)采集空間密度和時間頻率的飛越，數(shù)據(jù)獲取的觸角已伸向水利領(lǐng)域的方方面面，水利領(lǐng)域?qū)⒂瓉頂?shù)據(jù)的爆炸增長，水利大數(shù)據(jù)的時代已經(jīng)到來。

長期以來，由于數(shù)據(jù)和處理環(huán)境的限制，許多水利業(yè)務(wù)應(yīng)用的實時性和精準(zhǔn)性已經(jīng)很難滿足日益增長的分析需求。由于兼顧水利領(lǐng)域時空特征的大規(guī)模復(fù)雜結(jié)構(gòu)數(shù)據(jù)高效訪問方法的缺失，使得水利業(yè)務(wù)應(yīng)用無法直接使用極大豐富的數(shù)據(jù)資源。水利數(shù)據(jù)的時空分布依附于流域水系河網(wǎng)，具備非歐氏空間的語義距離。地理空間距離很近的兩個測站，由于分屬于不同流域，在數(shù)據(jù)分析時往往具有較遠的語義距離。目前對于具有非歐空間網(wǎng)絡(luò)拓撲關(guān)系數(shù)據(jù)研究較多地集中在智能交通領(lǐng)域[2-3]，所關(guān)注的移動對象數(shù)據(jù)分布在道路網(wǎng)中，關(guān)系多表現(xiàn)為具有交通約束的最近鄰、逆最近鄰等復(fù)雜關(guān)系[4-5]。不同于呈現(xiàn)時空數(shù)據(jù)流特性的路網(wǎng)移動對象數(shù)據(jù)，水利數(shù)據(jù)更多表現(xiàn)為具有水系河網(wǎng)關(guān)聯(lián)關(guān)系的時間序列集合，數(shù)據(jù)的查詢需要借助水系河網(wǎng)進行水系追蹤和產(chǎn)匯流區(qū)域查詢[6-8]，按照水系河網(wǎng)結(jié)構(gòu)的空間分布獲取相應(yīng)的數(shù)據(jù)。目前數(shù)字流域水系河網(wǎng)分析主要面向水文模擬需求提供產(chǎn)匯流空間區(qū)域[9]，將水系河網(wǎng)自身的管理處于次要地位，重點關(guān)注如何利用水系河網(wǎng)一次性生成的靜態(tài)產(chǎn)匯流空間區(qū)域范圍，而忽視了流域水系河網(wǎng)的索引和查詢效率。對數(shù)字流域水系河網(wǎng)要素的查詢需要對整個水系河網(wǎng)進行全集查找，限制動態(tài)查詢條件下的水系河網(wǎng)追蹤和產(chǎn)匯流子流域查詢的效率。為了解決上述問題，本文提出一種面向水系河網(wǎng)的建模與索引方法，首先對從地形數(shù)據(jù)中提取的水系河網(wǎng)建立圖論化模型；然后對河段進行外包建立水系河網(wǎng)索引BRR-Tree；最后結(jié)合典型水利數(shù)據(jù)訪問需求，設(shè)計水系河網(wǎng)查詢算法并進行實驗分析。

1 基于圖論的數(shù)字流域水系河網(wǎng)建模

流域水系河網(wǎng)是由若干支流逐步匯流到干流而形成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)[10]。本文在研究現(xiàn)有河網(wǎng)拓撲結(jié)構(gòu)的基礎(chǔ)上，采用有向圖來形式化描述流域河網(wǎng)空間拓撲結(jié)構(gòu)。如圖1所示，圖1a為實際河網(wǎng)，圖1b為相應(yīng)的圖論化模型。流域水系的空間實體由二維歐氏空間中最基本的節(jié)點、連線和多邊形及其組合構(gòu)成，其中節(jié)點是具有二維歐氏空間坐標(biāo)的點；連線是兩個節(jié)點之間的直線段，用以表征河道；多邊形是由首尾相連的若干條連線組成，其內(nèi)部是一個簡單連通多邊形區(qū)域，用以表征一個水系河網(wǎng)的連通分支。

圖1 流域水系的圖論化模型

在圖論化的流域水系模型中，如圖1所示水系河網(wǎng)的基本元素定義如下：

1) 河流源點，河流源點是河流發(fā)源點(圖中用空心圓表示)；

2) 匯合點，匯合點是不同支流匯合的地方，是流域河網(wǎng)生成時同時有兩個河道流入的交匯點，對于一個流域河網(wǎng)不存在兩條以上的支流在同一地點匯合(圖中用實心圓表示)；

3) 河道，即河流，河道分為內(nèi)部河道和外部河道，外部河道是河流源點與匯合點之間的河流，內(nèi)部河道則是除外部河道之外的河流；

4) 流域出口，整個流域的最下游，一個流域一般只有一個流域出口(圖中用同心圓表示)；

5) 河道折點，不具備匯水功能僅起水流傳輸作用的節(jié)點(圖中用三角形表示)。

水利領(lǐng)域不同類型、不同級別的應(yīng)用需不同詳細程度的水系河網(wǎng)信息[11]，需要在不同尺度水系河網(wǎng)間進行切換。商空間理論是人工智能領(lǐng)域處理不同粒度問題的新方法，它基于數(shù)學(xué)上的等價關(guān)系對形成分層遞階多粒度空間[12]，實現(xiàn)問題求解過程中的不同粒度世界之間的互相轉(zhuǎn)換。為了建立多尺度水系河網(wǎng)模型，本文將商空間理論引入到水系河網(wǎng)的建模中，借助商空間理論對問題的描述方法，定義多尺度等價關(guān)系和分層坐標(biāo)系，建立多比例尺的數(shù)字流域水系河網(wǎng)模型。

定義 1 流域水系：流域水系(basin river，BR)是一個擴展的有向圖BR=(V,E,f )，V是頂點集合用以表征水系河網(wǎng)特征點(包括河網(wǎng)折點、匯流點和出口)；E?V×V是邊集合用以表征水系河網(wǎng)中河道；f是屬性函數(shù)，用于定義河道的長度、集水面積和地理位置等。

定義 2 多尺度等價關(guān)系R(ci)：對于流域水系BR=(V,E,f )，給定一個條件序列(c0,c1,,ch)，?x,y∈E，xR(ci)y? xs.t.(c0,c1,,ci), ys.t.(c0,c1,,ci)，0≤i≤h。

定義2中的條件序列可以是水利領(lǐng)域的流域水系分級，或者水利專題地圖制作過程中不同比例尺間地圖的綜合原則，這由水文站網(wǎng)規(guī)劃決定，對此本文不做詳細研究，在此僅給出形式化描述。對應(yīng)于文獻[11]多尺度目錄層次樹的劃分條件，通過定義不同的條件序列c1

定義 3 水系河網(wǎng)特征點分層坐標(biāo)：對于一個水系河網(wǎng)特征點v∈V，其分層坐標(biāo)為一個向量=(vo,vi,,vn)對應(yīng)的分層映射：pvi:V→Vi是初始空間到商空間Vi的映射表示v在商空間Vi中被映射為下標(biāo)為k的對象，令vi=k。

河道和河網(wǎng)特征點分層坐標(biāo)系的建立，可以方便地進行水系河網(wǎng)的空間流向分析?；谏炭臻g分析的保假原理，通過先在粗粒度商空間進行河流的流向關(guān)系分析，剪枝大量不滿足條件的候選集，再對符合條件的子集進行細粒度計算以獲取相應(yīng)觀測設(shè)備的測量數(shù)據(jù)，這樣能夠極大地減少計算量。

2 基于河段的流域水系河網(wǎng)索引方法

在數(shù)字流域水系圖論化模型中，若直接選用河道作為索引的基本單元，存在數(shù)量多，容易增大索引結(jié)構(gòu)的體積。通過對水系河網(wǎng)的結(jié)構(gòu)分析可以發(fā)現(xiàn)，河網(wǎng)中的折點不會影響河網(wǎng)的匯水性，基于商空間理論建立多比例尺流域水系河網(wǎng)，將細粒度空間中的若干河道歸為一個等價類，進而綜合成為商空間中的一條河道，可以大大降低水系結(jié)構(gòu)分析和業(yè)務(wù)數(shù)據(jù)訪問的問題求解的復(fù)雜度。

定義 5 河段(river segment)：河段是由若干河道組成的輸水通道，在空間上表現(xiàn)為連接多個河網(wǎng)特征點而形成的折線段，一條河段除了端點外，不會與其他河段(或者河道)相交。

多尺度數(shù)字流域水系的圖論化表示模型中，河段是粗粒度商空間對細粒度商空間中若干河道的概化表示，選取河段作為索引的基本單元，既能減少索引結(jié)構(gòu)的體積，又可方便地支持河網(wǎng)流向分析。

在選定河段作為基本索引單元的基礎(chǔ)上，本文提出基于河段的流域水系索引結(jié)構(gòu)(BRR-Tree)，通過對R-Tree進行改進實現(xiàn)對數(shù)字流域水系的索引，通過對索引對象進行聚類形成最小外包矩形(minim building rectangle，MBR)建立索引，當(dāng)選取河段作為基本索引單元，對其外包操作如圖2所示。在完成對河段的MBR外包后，可以利用R-Tree的構(gòu)建算法對各個單元MBR的迭代外包，實現(xiàn)數(shù)字流域水系索引結(jié)構(gòu)的構(gòu)建。

圖2 河段的MBR外包

利用MBR對河段進行外包后，可以通過定義MBR間的關(guān)系來分析河段之間的地理位置關(guān)系。對于數(shù)字流域水系的結(jié)構(gòu)分析，不僅需要分析地理位置關(guān)系，還需要分析河段(或者河道)流向關(guān)系，為此BRR-Tree還需記錄具體的河道信息。BRR-Tree采用一個河段信息表(river segment information table，RSIT)保存河段中的河道和河網(wǎng)特征點。

定義 6 河段信息表：河段信息表是一個四元組RSIT=(Channel, Point_S, Point_E, Channel_O)，分別表示河道、河道起點、河道終點和流向河道。

如圖3所示，RSIT將Channel、Point_S、Point_E和Channel_O按需組織成為一個元組，按照河水流方向順序?qū)懭?，并將河段的起始河道在河道信息文件中的偏移量與該條河段中河道的數(shù)量作為河段的屬性特征值。

圖3 河段信息表結(jié)構(gòu)示意

河段信息表相當(dāng)于河道的分層坐標(biāo)，它記錄了河道與河段之間的對應(yīng)關(guān)系。通過建立河段信息表，保留了河段中河道的地理信息和相關(guān)關(guān)系，便于進行河網(wǎng)結(jié)構(gòu)分析和獲取具體的河段信息，實現(xiàn)非歐空間查詢與歐氏空間查詢的轉(zhuǎn)換。圖4所示為BRR-Tree的索引結(jié)構(gòu)，在BRR-Tree的上層節(jié)點中，主要存儲河段的MBR和指向下層節(jié)點的指針ptr。在葉子節(jié)點層，每個葉子節(jié)點對應(yīng)于一條河道，記錄有河段的描述信息。

定義 7 葉子節(jié)點：葉子節(jié)點是一個八元組：LN=(Seg,InSeg1,vid1,vid2,InSeg2,OutSeg,E_num, E_start_ptr)。其中：

1) Seg表示LN索引的河段；2) vid1和vid2分別為河段的起點和終點；3) InSeg1和InSeg2為河段，且有InSeg1flowto Seg和InSeg2flowto Seg，flowto表示流向關(guān)系，在圖論化的數(shù)字流域水系模型中，最多只有兩條河道同時匯流，所以河段的流入河段最多僅有兩條，若只有一條匯流河段時，不妨設(shè)其為InSeg1，當(dāng)InSeg1和InSeg2均為空時，表示該河段為外部河段；3) OutSeg為河段，且有Seg flowto OutSeg，并與Seg相交于點vid2；4) E_num表示河段中的河道的數(shù)量；5) E_start_ptr表示第一條河道在RSIT中的編號。

通過對河段利用MBR進行外包，能夠?qū)⒑佣畏庋b成R-Tree對應(yīng)的節(jié)點項，進而可以利用R-Tree的插入、查詢和刪除等算法實現(xiàn)BRR-Tree的基本操作。通過存儲vid1和vid2能夠?qū)⒑佣螌ν夥庋b成一條透明的河道，形成粗粒度的商空間、索引和查詢的對象，提高查詢效率。同時，通過InSeg1和InSeg2信息以及RSIT，又能有效地支撐進行細粒度的河網(wǎng)結(jié)構(gòu)分析，實現(xiàn)非歐查詢與歐氏空間查詢的轉(zhuǎn)換。

圖4 BRR-Tree索引結(jié)構(gòu)

3 基于BRR-Tree的水系河網(wǎng)查詢算法

水系河網(wǎng)的非歐結(jié)構(gòu)限制了水利領(lǐng)域數(shù)據(jù)的訪問效率，本文通過定義河段查詢、水流追蹤查詢和產(chǎn)匯流區(qū)域查詢3類查詢算法對水系河網(wǎng)進行分析，按照水系河網(wǎng)的訪問需求轉(zhuǎn)換歐氏空間的訪問需求，利用現(xiàn)有數(shù)據(jù)索引方法進行數(shù)據(jù)查詢。

3.1 河段查詢

定義 8 河段查詢(river query，RQ)： 給定一個空間查詢區(qū)域QR(query region)(空間點P)，從BRR-Tree中查詢出與QR相交(MBR包含P)的河段。

RQ查詢是基礎(chǔ)的流域水系河網(wǎng)分析查詢方法，在水利GIS應(yīng)用中，需要顯示某個視野范圍內(nèi)河流情況，這就需要獲取相關(guān)水系河網(wǎng)結(jié)構(gòu)。RQ查詢支持給定空間范圍QR和一個河網(wǎng)特征點P兩種查詢條件進行查詢，輸入條件是區(qū)域QR的RQ查詢過程如算法1所示(記為區(qū)域河段查詢，Region _RQ)，查詢首先從BRR-Tree的根節(jié)點開始，遞歸所有索引空間與查詢條件相交的子樹，查詢到葉節(jié)點時(一個葉節(jié)點對應(yīng)于一條河段)，利用葉節(jié)點記錄的河道偏移量讀取RSIT中相應(yīng)的河道，并將與QR相交的河道添加到結(jié)果集RS中。

算法1 區(qū)域河道查詢算法。Algorithm Region_RQ(QR,N)

輸入：空間查詢范圍(QR)，BRR-Tree節(jié)點(N)；輸出：與QR相交河道集合(RS)。

If(N is LeafNode)Then //葉子節(jié)點處理

For(i=N.E_start_ptr,i≤E_start_ptr+E_num;

i++)Do If(RSI.get(i).MBR Overlap QR )Then

RS.Add(RSI.get(i));

EndIf

RQ(QR,N.ptri); EndForEach EndIf

Return RS;

對于輸入條件是空間點P的河段查詢(記為點河段查詢Piont_RQ)流程與Region _RQ算法類似，區(qū)別在于葉子節(jié)點處理時直接將河段加入結(jié)果集。對于算法1通過去掉第4行語句中的條件判斷，RQ查詢也可以返回與查詢條件QR相交的完整河段(即返回該條河段中的所有河道)，相關(guān)細節(jié)本文不再贅述。

3.2 水系追蹤查詢

定義 9 水系追蹤查詢(river track query，RTQ)：對于給定的兩個河網(wǎng)特征點ps和pe(分別表示上、下游)，查詢流域水系中p1～p2的河段。

RTQ的查詢過程如算法2所示，由于流域水系是形式描述成為若干局部連通分支構(gòu)成的有向圖，對于輸入的Ps和Pe，首先需要判斷其是否在同一個連通分支中。算法利用Ps和Pe在商空間鏈的分層坐標(biāo)系獲取粗粒度商空間中對應(yīng)的對象，在粗粒度空間判斷連通性，若兩點不連通，則無需進行追蹤查詢，查詢結(jié)果為空。若Ps和Pe在同一個連通分支內(nèi)，則利用BRR-Tree獲取起始河段和終點河段，并利用葉子節(jié)點中保存的流出河段信息進行河段追蹤，并按照流向?qū)⒑佣螌懭虢Y(jié)果集。

算法2 水流追蹤查詢。

Algorithm RTQ(Ps, Pe, N)

加強對土壤的監(jiān)測和科技管理，是提高土壤耕地地力水平的重要措施。相關(guān)部門必須要明確自身的職責(zé)，加強土壤監(jiān)測力度。同時還需要加強對土壤監(jiān)測過程中的科技投入，成立專門的監(jiān)測調(diào)查小組，加強對土壤質(zhì)量的調(diào)查和監(jiān)測，形成長期跟蹤監(jiān)測機制。一旦發(fā)現(xiàn)土壤出現(xiàn)被污染的情況，要及時對土壤進行治理，減少土壤的耕作量，等到土壤條件恢復(fù)之后再進行耕作。

輸入：查詢起點和終點(Ps和Pe)，BRR-Tree節(jié)點(N)；

輸出：Ps到Pe的河段集合(RS)。

利用分層坐標(biāo)獲取Ps最粗粒度商空間的坐標(biāo)sP′；利用分層坐標(biāo)獲取Pe最粗粒度商空間的坐標(biāo)eP′；計算sP′和eP′的連通性，計算結(jié)果記為flag。

If(flag==FALSE)Then

Return NULL;

EndIf

Segs= Piont_RQ (Ps, N) ;//獲取開始河段

Sege= Piont_RQ (Pe, N); //獲取結(jié)束河段

RS.Add(Segs);

Seg_Temp=Segs.OutSeg；

RS.Add(Seg_Temp);

Seg_Temp= Seg_Temp.OutSeg;

EndWhile

RS.Add(Sege);

Return RS;

3.3 子流域追蹤查詢

定義 10 子流域追蹤查詢(sub basin query，SBQ)：給定一個空間查詢范圍QR(查詢點P)，利用河網(wǎng)獲取匯流到區(qū)域QR(點P)的河段集合。

根據(jù)地表徑流的產(chǎn)匯流原理，河道中的水來源于其整個產(chǎn)匯流區(qū)域，SBQ的功能是實現(xiàn)查詢條件對應(yīng)產(chǎn)匯流區(qū)的獲取。首先利用河段查詢算法從BRR-Tree獲取流入河段；然后利用流入河段(InSeg1和InSeg2)進行回溯；最終獲取產(chǎn)匯流區(qū)域的全部河道。本文基于商空間理論，通過定義河段作為索引的基本單元，能有效地縮小搜索空間的大小(回溯追蹤的隊列長度)，提高回溯追蹤的效率。SBQ查詢與河段查詢支持點查詢和區(qū)域查詢一樣支持點查詢和區(qū)域查詢，SBQ點查詢過程(Piont_SBQ)的形式化描述如算法3所示。

算法3 點子流域追蹤查詢算法。

Algorithm Piont_SBQ(P,N)

輸入：河網(wǎng)特征點(P)，BRR-Tree節(jié)點(N)；

輸出：匯流到P的子流域水系河段集合(RS)。

Define：Q；//追蹤回溯隊列定義；

Define：Seg；//河段臨時變量；

Seg=Point_RQ(P,N);

Q.Add(Seg);

While(Q is not NULL)Do

Seg=Q.First();

Q.Remove(Seg);

If(Seq. InSeg1is not NULL)Then

RS.Add(Seg);

Q.Add(Seg.InSeg1);

EndIf

If(Seq. InSeg2is not NULL)Then

Q.Add(Seg.InSeg2);

EndIf

Return RS;

SBQ區(qū)域查詢的查詢過程與SBQ點查詢類似，不同之處在于第3行語句，前者調(diào)用Point_RQ查詢算法獲取河段，后者調(diào)用Region_RQ查詢算法獲取河段。Region_RQ查詢返回的可能是一個河段集合，算法統(tǒng)一將其加入到回溯追蹤隊列中，然后進行子流域追蹤。

4 實驗分析

為了驗證BRR-Tree的索引效果，本文選取8組TIN數(shù)據(jù)，利用文獻[12]中的方法提取水系河網(wǎng)，然后建立河網(wǎng)建模與索引，實驗從索引空間大小和查詢效率等方面進行分析。實驗系統(tǒng)配置：CPU，i5-2450M 2.50 GHz；RAM，4.00 GB；OS，Win7。

4.1 索引空間大小分析

圖5 相同河網(wǎng)中索引單元數(shù)量的比較

BRR-Tree的基本索引單元是河段，不失一般性，在實驗中將兩個匯流點之間的河道定義為河段，并采用ArcGis shp文件進行存儲，圖5所示為全部8組實驗數(shù)據(jù)集河道和河段數(shù)量的對比圖?？梢园l(fā)現(xiàn)對河段進行索引能夠有效減少索引體積，面對大規(guī)模河網(wǎng)索引時，相對于直接索引河道(CHR-Tree)，BRR-Tree較小的索引體積可以直接將中間節(jié)點讀入內(nèi)存，減少查詢過程中的磁盤I/O次數(shù)，提高查詢處理效率。

4.2 索引查詢效率分析

建立BRR-Tree的目的是實現(xiàn)非歐查詢到歐氏空間查詢的轉(zhuǎn)換，主要由水系追蹤查詢(算法2)和產(chǎn)匯流區(qū)域查詢(算法3)實現(xiàn)。分析算法2和算法3可以發(fā)現(xiàn)，其關(guān)鍵是利用算法1進行河段(河道)的快速查詢，然后通過索引中的流入和流出河段進行水系追蹤和產(chǎn)匯流區(qū)域的查詢。在利用算法1進行河道查詢時，BRR-Tree索引查詢速度優(yōu)于未建立索引的shp全表掃描。為此，不失一般性，本文選取算法3分析索引的效率。

圖6 水系追蹤查詢的時間效率分析

圖6所示是對不同數(shù)據(jù)規(guī)模的水系河網(wǎng)進行水系追蹤查詢的時間開銷，由于同一數(shù)據(jù)集河段的數(shù)量小于河道的數(shù)量，且文獻[12]的河網(wǎng)提取的河道與TIN數(shù)據(jù)的三角形和邊數(shù)量相關(guān)，因此圖中的問題規(guī)模采用TIN三角形數(shù)量和邊的數(shù)量。由于采用河段封裝若干河道，BRR-Tree的葉節(jié)點數(shù)量小于CHR-Tree，在進行水系追蹤查詢BRR-Tree的查詢效率將優(yōu)于CHR-Tree。直接訪問是直接從shp文件中讀取數(shù)據(jù)，需要全表掃描判斷流入和流出河段，完成一次查詢需要的時間遠高于BRR-Tree和CHR-Tree，所以縱坐標(biāo)的查詢時間采用以10為底的對數(shù)進行處理后的時間值。河段直接訪問的查詢時間與整個問題規(guī)模相關(guān)，在問題規(guī)模增長時，查詢時間增長速度較快。BRR-Tree通過提前對數(shù)字流域水系河網(wǎng)的流入和流出關(guān)系進行建模，建立了河段間的流向?qū)?yīng)關(guān)系，查詢時間相對于問題規(guī)模增長的速度增長緩慢，僅僅與具有流向關(guān)系河段子集規(guī)模相關(guān)，為此在圖6中部分區(qū)間的索引查詢時間不隨著問題規(guī)模的增加而增加(或者增加非常緩慢)，具有良好的時間復(fù)雜度。

5 結(jié) 束 語

本文以提高水利領(lǐng)域數(shù)據(jù)的高效訪問為目的展開研究，對水系河網(wǎng)進行建模與索引，實現(xiàn)水利領(lǐng)域非歐查詢請求到歐氏空間查詢請求的轉(zhuǎn)換。將領(lǐng)域知識與大數(shù)據(jù)的研究相結(jié)合是目前大數(shù)據(jù)研究領(lǐng)域的熱點問題，本文利用水系河網(wǎng)表達領(lǐng)域時空特征，通過定義水利領(lǐng)域典型的水系河網(wǎng)查詢算法進行理論和方法的探索，下一步還需要豐富與完善更多的水系河網(wǎng)分析算法以及解決大數(shù)據(jù)背景下異構(gòu)水利業(yè)務(wù)數(shù)據(jù)的高效索引問題。

[1] 水利部水利信息化工作領(lǐng)導(dǎo)小組辦公室. 2012年度中國水利信息化發(fā)展報告[M]. 北京: 中國水利水電出版社, 2013. Leadership Group Office of the Information Explosion Process of Water Industry. 2012 China water conservancy informatization development report[M]. Beijing: China WaterPower Press, 2013.

[2] FENG Jun, LU Chun-yan, WANG Ying, et al. Sketch RR-Tree: a spatio-temporal aggregation index for networkconstrained moving objects[C]//Proceedings of the 3rd International Conference on Innovative Computing Information and Control. Dalian: IEEE, 2008: 4-7.

[3] CUDRE-MAUROUX P, WU E, MADDEN S. TrajStore: an adaptive storage system for very large trajectory data sets[C]//Proceedings of the 26th International Conference on Data Engineering. Long Beach, CA, USA: IEEE , 2010: 109-120.

[4] FENG J, WU L, ZHU Y, et al. Continuous k-nearest neighbor search under mobile environment[C]//Proceedings of the 9th Asia-Pacific Web Conference on Advances in Data and Web Management, APWeb 2007 and 8th International Conference on Web-Age Information Management. Berlin Heidelberg: Springer, 2007: 566-573.

[5] GüTING R H, BEHR T, XU J. Efficient k-nearest neighbor search on moving object trajectories[J]. The VLDB Journal, 2010, 19(5): 687-714.

[6] TANG Fu-ping, LI Man-chun, QIN Fen. Distributed rainfall-run off simulating based on cellular automata for small water sheds[J]. Advances in Water Science, 2010, 21(2): 173-178.

[7] TANG Hong-wu, LEI Yan, GU Zheng-hua. Intelligence simulation technique for river net flow and its application[J]. Advances in Water Science, 2008, 19(2): 232-237.

[8] WANG X M, HAO R, HUO J, et al. Modeling sediment transport in river networks[J]. Physica A: Statistical Mechanics and its Applications, 2008, 387(25): 6421-6430.

[9] QU G D, SU D Y, LOU Z H. A new algorithm to automatically extract the drainage networks and catchments based on triangulation irregular network digital elevation model[J]. Journal of Shanghai Jiaotong University (Science), 2014, 19(3): 367-377.

[10] 劉學(xué)軍, 王永君, 任政, 等. 基于不規(guī)則三角網(wǎng)的河網(wǎng)提取算法[J]. 水利學(xué)報, 2008, 39(1): 27-34. LIU Xue-jun, WANG Yong-jun, REN Zheng, et al. Algorithm for extracting drainage network based on triangulated irregular network[J]. Journal of Hydraulic Engineering, 2008, 39(1) : 27-34.

[11] 馮鈞, 朱躍龍, 徐建峰. 多專題多比例尺水系河網(wǎng)管理模型研究[J]. 水利學(xué)報, 2007, 38(11): 1371-1376. FENG Jun, ZHU Yue-long, XU Jian-feng. Multi-theme and multi-scale river networks management model[J]. Journal of Hydraulic Engineering, 2007, 38(11): 1371-1376.

[12] 張鈴, 張鈸. 模糊商空間理論(模糊粒度計算方法)[J].軟件學(xué)報, 2003, 14(4): 770-776. ZHANG Ling, ZHANG Bo. Theory of fuzzy quotient space (methods of fuzzy granular computing)[J]. Journal of Software, 2003, 14(4): 770-776.

[13] 馮鈞, 唐志賢, 朱躍龍, 等. 一種基于TIN數(shù)據(jù)的河網(wǎng)提取方法[P]. 中國: 201110115791, 2012-12-05. FENG Jun, TANG Zhi-xian, ZHU Yue-long, et al. An river extraction method based on TIN data[P]. China: 201110115791, 2012-12-05.

編輯漆 蓉

Research on the Modeling and Indexing Method for River Network

TANG Zhi-xian1, FENG Jun1, XU Xi1, and SHI Ya-qing1,2
(1. College of Computer and Information, Hohai University Nanjing 211110; 2. Institute of Command Information Systems, PLA University of Science and Technology Nanjing 210007)

The water conservancy data appears as the sets of river-network-based time series, the data queries usually need to obtain the corresponding data according to the spatial distribution of the river network’s structure. Regarding the problem that the river network’s non-Euclidean spatial features limit the data query efficiency, this paper builds the river network’s multi-scale graph theory model based on the quotient space theory first, then selects the river segments as the query units to construct the river network’s indexes basin river R-tree (BRR-Tree), designs the typical query algorithm of the river network. The algorithm converts the non-Euclidean data access requests into the ones meeting the Euclidean spatial features. The experiments show that the method proposed in this paper can effectively support the river network’s analysis and improve data access efficiency in water conservancy field.

index; modeling; river network; river segment

TP391

A doi:10.3969/j.issn.1001-0548.2015.04.023

2014 ? 10 ? 13；

2015 ? 04 ?15

國家自然科學(xué)基金(61370091, 61170200)；江蘇省科技支撐計劃(工業(yè))(BE2012179)

唐志賢(1983 ? )，男，博士生，主要從事時空數(shù)據(jù)索引方面的研究.