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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義 2 多尺度等價(jià)關(guān)系R(ci)：對(duì)于流域水系BR=(V,E,f )，給定一個(gè)條件序列(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)域的流域水系分級(jí)，或者水利專(zhuān)題地圖制作過(guò)程中不同比例尺間地圖的綜合原則，這由水文站網(wǎng)規(guī)劃決定，對(duì)此本文不做詳細(xì)研究，在此僅給出形式化描述。對(duì)應(yīng)于文獻(xiàn)[11]多尺度目錄層次樹(shù)的劃分條件，通過(guò)定義不同的條件序列c1

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

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

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

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

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

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

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

圖2 河段的MBR外包

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

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

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

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

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

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

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

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

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

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

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

3.1 河段查詢(xún)

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

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

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

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

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

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;

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

3.2 水系追蹤查詢(xún)

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

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

算法2 水流追蹤查詢(xún)。

Algorithm RTQ(Ps, Pe, N)

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

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

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

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

If(flag==FALSE)Then

Return NULL;

EndIf

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

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 子流域追蹤查詢(xún)

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

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

算法3 點(diǎn)子流域追蹤查詢(xún)算法。

Algorithm Piont_SBQ(P,N)

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

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

Define：Q；//追蹤回溯隊(duì)列定義；

Define：Seg；//河段臨時(shí)變量；

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ū)域查詢(xún)的查詢(xún)過(guò)程與SBQ點(diǎn)查詢(xún)類(lèi)似，不同之處在于第3行語(yǔ)句，前者調(diào)用Point_RQ查詢(xún)算法獲取河段，后者調(diào)用Region_RQ查詢(xún)算法獲取河段。Region_RQ查詢(xún)返回的可能是一個(gè)河段集合，算法統(tǒng)一將其加入到回溯追蹤隊(duì)列中，然后進(jìn)行子流域追蹤。

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

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

4.1 索引空間大小分析

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

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

4.2 索引查詢(xún)效率分析

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

圖6 水系追蹤查詢(xún)的時(shí)間效率分析

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

5 結(jié) 束 語(yǔ)

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

[1] 水利部水利信息化工作領(lǐng)導(dǎo)小組辦公室. 2012年度中國(guó)水利信息化發(fā)展報(bào)告[M]. 北京: 中國(guó)水利水電出版社, 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é)報(bào), 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] 馮鈞, 朱躍龍, 徐建峰. 多專(zhuān)題多比例尺水系河網(wǎng)管理模型研究[J]. 水利學(xué)報(bào), 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ì)算方法)[J].軟件學(xué)報(bào), 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]. 中國(guó): 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

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

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