水利行业长期的业务实践积累了大量分布异构独立的业务数据^[1]，随着以物联网、云计算、移动互联网和RS技术为基础的智慧水利规划的实施，逐步形成天地一体的水利监测体系^[1]，将带来数据采集空间密度和时间频率的飞越，数据获取的触角已伸向水利领域的方方面面，水利领域将迎来数据的爆炸增长，水利大数据的时代已经到来。

长期以来，由于数据和处理环境的限制，许多水利业务应用的实时性和精准性已经很难满足日益增长的分析需求。由于兼顾水利领域时空特征的大规模复杂结构数据高效访问方法的缺失，使得水利业务应用无法直接使用极大丰富的数据资源。水利数据的时空分布依附于流域水系河网，具备非欧氏空间的语义距离。地理空间距离很近的两个测站，由于分属于不同流域，在数据分析时往往具有较远的语义距离。目前对于具有非欧空间网络拓扑关系数据研究较多地集中在智能交通领域^{[2, 3]}，所关注的移动对象数据分布在道路网中，关系多表现为具有交通约束的最近邻、逆最近邻等复杂关系^{[4, 5]}。不同于呈现时空数据流特性的路网移动对象数据，水利数据更多表现为具有水系河网关联关系的时间序列集合，数据的查询需要借助水系河网进行水系追踪和产汇流区域查询^{[6, 7, 8]}，按照水系河网结构的空间分布获取相应的数据。目前数字流域水系河网分析主要面向水文模拟需求提供产汇流空间区域^[9]，将水系河网自身的管理处于次要地位，重点关注如何利用水系河网一次性生成的静态产汇流空间区域范围，而忽视了流域水系河网的索引和查询效率。对数字流域水系河网要素的查询需要对整个水系河网进行全集查找，限制动态查询条件下的水系河网追踪和产汇流子流域查询的效率。为了解决上述问题，本文提出一种面向水系河网的建模与索引方法，首先对从地形数据中提取的水系河网建立图论化模型；然后对河段进行外包建立水系河网索引BRR-Tree；最后结合典型水利数据访问需求，设计水系河网查询算法并进行实验分析。

流域水系河网是由若干支流逐步汇流到干流而形成的网络拓扑结构^[10]。本文在研究现有河网拓扑结构的基础上，采用有向图来形式化描述流域河网空间拓扑结构。如图 1所示，图 1a为实际河网，图 1b为相应的图论化模型。流域水系的空间实体由二维欧氏空间中最基本的节点、连线和多边形及其组合构成，其中节点是具有二维欧氏空间坐标的点；连线是两个节点之间的直线段，用以表征河道；多边形是由首尾相连的若干条连线组成，其内部是一个简单连通多边形区域，用以表征一个水系河网的连通分支。

图1

图1流域水系的图论化模型

在图论化的流域水系模型中，如图 1所示水系河网的基本元素定义如下：

1) 河流源点，河流源点是河流发源点(图中用空心圆表示)；

2) 汇合点，汇合点是不同支流汇合的地方，是流域河网生成时同时有两个河道流入的交汇点，对于一个流域河网不存在两条以上的支流在同一地点汇合(图中用实心圆表示)；

3) 河道，即河流，河道分为内部河道和外部河道，外部河道是河流源点与汇合点之间的河流，内部河道则是除外部河道之外的河流；

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

5) 河道折点，不具备汇水功能仅起水流传输作用的节点(图中用三角形表示)。

水利领域不同类型、不同级别的应用需不同详细程度的水系河网信息^[11]，需要在不同尺度水系河网间进行切换。商空间理论是人工智能领域处理不同粒度问题的新方法，它基于数学上的等价关系对形成分层递阶多粒度空间^[12]，实现问题求解过程中的不同粒度世界之间的互相转换。为了建立多尺度水系河网模型，本文将商空间理论引入到水系河网的建模中，借助商空间理论对问题的描述方法，定义多尺度等价关系和分层坐标系，建立多比例尺的数字流域水系河网模型。

定义 1 流域水系：流域水系(basin river，BR)是一个扩展的有向图 ${\rm{BR}} = (V,E,f)$，V是顶点集合用以表征水系河网特征点(包括河网折点、汇流点和出口)； $E \subset V \times V$是边集合用以表征水系河网中河道；f是属性函数，用于定义河道的长度、集水面积和地理位置等。

定义 2 多尺度等价关系 $R({c_i})$：对于流域水系 ${\rm{BR}} = (V,E,f)$，给定一个条件序列 $({c_0},{c_1}, \cdots ,{c_h})$， $\forall x,y \in E$， $x\;R({c_i})\;y \Leftrightarrow $ $x\;{\rm{s}}{\rm{.t}}{\rm{.}}\;({c_0},{c_1}, \cdots ,{c_i})$, $y\;{\rm{s}}{\rm{.t}}{\rm{.}}\;({c_0},{c_1}, \cdots ,{c_i})$， $0 \le i \le h$。

定义2中的条件序列可以是水利领域的流域水系分级，或者水利专题地图制作过程中不同比例尺间地图的综合原则，这由水文站网规划决定，对此本文不做详细研究，在此仅给出形式化描述。对应于文献^[11]多尺度目录层次树的划分条件，通过定义不同的条件序列 ${c_1} < {c_2} < \cdots < {c_n}$，构造出相应的等价关系簇： $R({c_i}),1 \le i \le h$，则可以构建出不同粒度的商空间链(即多尺度水系河网模型)： $(V,E,f) < ({V_1},{E_1},{f_1}) < ({V_2},{E_2},{f_2}) < \cdots < ({V_h},{E_h},{f_h})$， $({V_i},{E_i},{f_i})\;0 \le i \le h$对应于不同尺度的河网。在进行河网建模和地图表达时，需要在不同比例尺之间进行切换，如从流域级别切换到子流域级别，这就需要建立不同粒度商空间中对象的对应关系，本文下面将通过定义分层坐标系建立河网特征点和河道在不同商空间的关联关系。

定义 3 水系河网特征点分层坐标：对于一个水系河网特征点 $v \in V$，其分层坐标为一个向量 $\bar v = ({v_0},{v_1}, \cdots ,{v_n})$对应的分层映射： $p{v_i}(v){\rm{ = }}v_k^i,v \in V$是初始空间到商空间 ${V^i}$的映射， $p{v_i}(v){\rm{ = }}v_k^i,v \in V$，表示v在商空间 ${V^i}$中被映射为下标为k的对象，令 ${v_i} = k$。

定义 4 水系河网河道分层坐标：对于一条河道 $e \in E$，令 $\bar e = ({e_0},{e_1}, \cdots ,{e_n})$为e的分层坐标，对应的分层映射 $p{e_i}:E \to {E^i}$是初始空间到商空间 ${E^i}$映射， $p{e_i}(e){\rm{ = }}e_k^i,e \in E$，表示e在商空间 ${E^i}$中被映射为下标为k的对象，令 ${e_i} = k$。

河道和河网特征点分层坐标系的建立，可以方便地进行水系河网的空间流向分析。基于商空间分析的保假原理，通过先在粗粒度商空间进行河流的流向关系分析，剪枝大量不满足条件的候选集，再对符合条件的子集进行细粒度计算以获取相应观测设备的测量数据，这样能够极大地减少计算量。

在数字流域水系图论化模型中，若直接选用河道作为索引的基本单元，存在数量多，容易增大索引结构的体积。通过对水系河网的结构分析可以发现，河网中的折点不会影响河网的汇水性，基于商空间理论建立多比例尺流域水系河网，将细粒度空间中的若干河道归为一个等价类，进而综合成为商空间中的一条河道，可以大大降低水系结构分析和业务数据访问的问题求解的复杂度。

定义 5 河段(river segment)：河段是由若干河道组成的输水通道，在空间上表现为连接多个河网特征点而形成的折线段，一条河段除了端点外，不会与其他河段(或者河道)相交。

多尺度数字流域水系的图论化表示模型中，河段是粗粒度商空间对细粒度商空间中若干河道的概化表示，选取河段作为索引的基本单元，既能减少索引结构的体积，又可方便地支持河网流向分析。

在选定河段作为基本索引单元的基础上，本文提出基于河段的流域水系索引结构(BRR-Tree)，通过对R-Tree进行改进实现对数字流域水系的索引，通过对索引对象进行聚类形成最小外包矩形(minim building rectangle，MBR)建立索引，当选取河段作为基本索引单元，对其外包操作如图 2所示。在完成对河段的MBR外包后，可以利用R-Tree的构建算法对各个单元MBR的迭代外包，实现数字流域水系索引结构的构建。

图2

图2河段的MBR外包

利用MBR对河段进行外包后，可以通过定义MBR间的关系来分析河段之间的地理位置关系。对于数字流域水系的结构分析，不仅需要分析地理位置关系，还需要分析河段(或者河道)流向关系，为此BRR-Tree还需记录具体的河道信息。BRR-Tree采用一个河段信息表(river segmentinformation table，RSIT)保存河段中的河道和河网特征点。

定义 6 河段信息表：河段信息表是一个四元组RSIT=(Channel,Point_S, Point_E, Channel_O)，分别表示河道、河道起点、河道终点和流向河道。

如图 3所示，RSIT将Channel、Point_S、Point_E和Channel_O按需组织成为一个元组，按照河水流方向顺序写入，并将河段的起始河道在河道信息文件中的偏移量与该条河段中河道的数量作为河段的属性特征值。

图3

图3河段信息表结构示意

河段信息表相当于河道的分层坐标，它记录了河道与河段之间的对应关系。通过建立河段信息表，保留了河段中河道的地理信息和相关关系，便于进行河网结构分析和获取具体的河段信息，实现非欧空间查询与欧氏空间查询的转换。图 4所示为BRR-Tree的索引结构，在BRR-Tree的上层节点中，主要存储河段的MBR和指向下层节点的指针ptr。在叶子节点层，每个叶子节点对应于一条河道，记录有河段的描述信息。

定义 7 叶子节点：叶子节点是一个八元组： LN=(Seg,InSeg₁,vid₁,vid₂,InSeg₂,OutSeg,E_num, E_start_ptr)。其中：

1) Seg表示LN索引的河段；2) ${\rm{vi}}{{\rm{d}}_{\rm{1}}}$和${\rm{vi}}{{\rm{d}}_{\rm{2}}}$分别为河段的起点和终点；3) InSeg₁和InSeg₂为河段，且有InSeg₁ flowtoSeg和InSeg₂ flowto Seg，flowto表示流向关系，在图论化的数字流域水系模型中，最多只有两条河道同时汇流，所以河段的流入河段最多仅有两条，若只有一条汇流河段时，不妨设其为InSeg₁，当InSeg₁和InSeg₂均为空时，表示该河段为外部河段；3) OutSeg为河段，且有Seg flowto OutSeg，并与Seg相交于点${\rm{vi}}{{\rm{d}}_{\rm{2}}}$；4) E_num表示河段中的河道的数量；5) E_start_ptr表示第一条河道在RSIT中的编号。

通过对河段利用MBR进行外包，能够将河段封装成R-Tree对应的节点项，进而可以利用R-Tree的插入、查询和删除等算法实现BRR-Tree的基本操作。通过存储vid₁和vid₂能够将河段对外封装成一条透明的河道，形成粗粒度的商空间、索引和查询的对象，提高查询效率。同时，通过InSeg₁和InSeg₂信息以及RSIT，又能有效地支撑进行细粒度的河网结构分析，实现非欧查询与欧氏空间查询的转换。

图4

图4BRR-Tree索引结构

水系河网的非欧结构限制了水利领域数据的访问效率，本文通过定义河段查询、水流追踪查询和产汇流区域查询3类查询算法对水系河网进行分析，按照水系河网的访问需求转换欧氏空间的访问需求，利用现有数据索引方法进行数据查询。

定义 8 河段查询(river query，RQ)： 给定一个空间查询区域QR(query region)(空间点P)，从BRR-Tree中查询出与QR相交(MBR包含P)的河段。

RQ查询是基础的流域水系河网分析查询方法，在水利GIS应用中，需要显示某个视野范围内河流情况，这就需要获取相关水系河网结构。RQ查询支持给定空间范围QR和一个河网特征点P两种查询条件进行查询，输入条件是区域QR的RQ查询过程如算法1所示(记为区域河段查询，Regio _RQ)，查询首先从BRR-Tree的根节点开始，递归所有索引空间与查询条件相交的子树，查询到叶节点时(一个叶节点对应于一条河段)，利用叶节点记录的河道偏移量读取RSIT中相应的河道，并将与QR相交的河道添加到结果集RS中。

算法1 区域河道查询算法。

Algorithm Region_RQ(QR,N)

输入：空间查询范围(QR)，BRR-Tree节点(N)；

输出：与QR相交河道集合(RS)。

If(N is LeafNode)Then //叶子节点处理

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

EndFor

Else // 非叶子节点进行递归处理

ForEach(N.MBR(Segment_i)Overlap QR)Do

RQ(QR,N.ptr_i);

EndForEach

EndIf

Return RS;

对于输入条件是空间点P的河段查询(记为点河段查询Piont_RQ)流程与Region_RQ算法类似，区别在于叶子节点处理时直接将河段加入结果集。对于算法1通过去掉第4行语句中的条件判断，RQ查询也可以返回与查询条件QR相交的完整河段(即返回该条河段中的所有河道)，相关细节本文不再赘述。

定义 9 水系追踪查询(river track query，RTQ)：对于给定的两个河网特征点p_s和p_e(分别表示上、下游)，查询流域水系中p₁～p₂的河段。

RTQ的查询过程如算法2所示，由于流域水系是形式描述成为若干局部连通分支构成的有向图，对于输入的P_s和P_e，首先需要判断其是否在同一个连通分支中。算法利用P_s和P_e在商空间链的分层坐标系获取粗粒度商空间中对应的对象，在粗粒度空间判断连通性，若两点不连通，则无需进行追踪查询，查询结果为空。若P_s和P_e在同一个连通分支内，则利用BRR-Tree获取起始河段和终点河段，并利用叶子节点中保存的流出河段信息进行河段追踪，并按照流向将河段写入结果集。

算法2 水流追踪查询。

Algorithm RTQ(P_s, P_e, N)

输入：查询起点和终点(P_s和P_e)，BRR-Tree节点(N)；

输出：P_s到P_e的河段集合(RS)。

利用分层坐标获取P_s最粗粒度商空间的坐标${P_{\rm{s}}}^\prime $；利用分层坐标获取P_e最粗粒度商空间的坐标${P_{\rm{e}}}^\prime $；计算${P_{\rm{e}}}^\prime $和${P_{\rm{e}}}^\prime $的连通性，计算结果记为flag。

If(flag==FALSE)Then

Return NULL;

EndIf

Segs= Piont_RQ(P_s , N);//获取开始河段

Sege= Piont_RQ (P_e , N);//获取结束河段

RS.Add(Segs);

Seg_Temp=Segs.OutSeg；

While(Seg_Temp ≠ Sege)Do；

RS.Add(Seg_Temp);

Seg_Temp=Seg_Temp.OutSeg;

EndWhile

RS.Add(Sege);

Return RS;

定义 10 子流域追踪查询(sub basin query，SBQ)：给定一个空间查询范围QR(查询点P)，利用河网获取汇流到区域QR(点P)的河段集合。

根据地表径流的产汇流原理，河道中的水来源于其整个产汇流区域，SBQ的功能是实现查询条件对应产汇流区的获取。首先利用河段查询算法从BRR-Tree获取流入河段；然后利用流入河段(InSeg₁和InSeg₂)进行回溯；最终获取产汇流区域的全部河道。本文基于商空间理论，通过定义河段作为索引的基本单元，能有效地缩小搜索空间的大小(回溯追踪的队列长度)，提高回溯追踪的效率。SBQ查询与河段查询支持点查询和区域查询一样支持点查询和区域查询，SBQ点查询过程(Piont_SBQ)的形式化描述如算法3所示。

算法3 点子流域追踪查询算法。

Algorithm Piont_SBQ(P,N)

输入：河网特征点(P)，BRR-Tree节点(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. InSeg₁is not NULL)Then

RS.Add(Seg);

Q.Add(Seg.InSeg₁);

EndIf

If(Seq. InSeg₂ is not NULL)Then

Q.Add(Seg.InSeg₂);

EndIf

Return RS;

SBQ区域查询的查询过程与SBQ点查询类似，不同之处在于第3行语句，前者调用Point_RQ查询算法获取河段，后者调用Region_RQ查询算法获取河段。Region_RQ查询返回的可能是一个河段集合，算法统一将其加入到回溯追踪队列中，然后进行子流域追踪。

为了验证BRR-Tree的索引效果，本文选取8组TIN数据，利用文献^[12]中的方法提取水系河网，然后建立河网建模与索引，实验从索引空间大小和查询效率等方面进行分析。实验系统配置：CPU，i5-2450M2.50 GHz；RAM，4.00 GB；OS，Win7。

图5

图5相同河网中索引单元数量的比较

BRR-Tree的基本索引单元是河段，不失一般性，在实验中将两个汇流点之间的河道定义为河段，并采用ArcGis shp文件进行存储，图 5所示为全部8组实验数据集河道和河段数量的对比图。可以发现对河段进行索引能够有效减少索引体积，面对大规模河网索引时，相对于直接索引河道(CHR-Tree)，BRR-Tree较小的索引体积可以直接将中间节点读入内存，减少查询过程中的磁盘I/O次数，提高查询处理效率。

建立BRR-Tree的目的是实现非欧查询到欧氏空间查询的转换，主要由水系追踪查询(算法2)和产汇流区域查询(算法3)实现。分析算法2和算法3可以发现，其关键是利用算法1进行河段(河道)的快速查询，然后通过索引中的流入和流出河段进行水系追踪和产汇流区域的查询。在利用算法1进行河道查询时，BRR-Tree索引查询速度优于未建立索引的shp全表扫描。为此，不失一般性，本文选取算法3分析索引的效率。

图6

图6水系追踪查询的时间效率分析

图 6所示是对不同数据规模的水系河网进行水系追踪查询的时间开销，由于同一数据集河段的数量小于河道的数量，且文献^[12]的河网提取的河道与TIN数据的三角形和边数量相关，因此图中的问题规模采用TIN三角形数量和边的数量。由于采用河段封装若干河道，BRR-Tree的叶节点数量小于CHR-Tree，在进行水系追踪查询BRR-Tree的查询效率将优于CHR-Tree。直接访问是直接从shp文件中读取数据，需要全表扫描判断流入和流出河段，完成一次查询需要的时间远高于BRR-Tree和CHR-Tree，所以纵坐标的查询时间采用以10为底的对数进行处理后的时间值。河段直接访问的查询时间与整个问题规模相关，在问题规模增长时，查询时间增长速度较快。BRR-Tree通过提前对数字流域水系河网的流入和流出关系进行建模，建立了河段间的流向对应关系，查询时间相对于问题规模增长的速度增长缓慢，仅仅与具有流向关系河段子集规模相关，为此在图 6中部分区间的索引查询时间不随着问题规模的增加而增加(或者增加非常缓慢)，具有良好的时间复杂度。

本文以提高水利领域数据的高效访问为目的展开研究，对水系河网进行建模与索引，实现水利领域非欧查询请求到欧氏空间查询请求的转换。将领域知识与大数据的研究相结合是目前大数据研究领域的热点问题，本文利用水系河网表达领域时空特征，通过定义水利领域典型的水系河网查询算法进行理论和方法的探索，下一步还需要丰富与完善更多的水系河网分析算法以及解决大数据背景下异构水利业务数据的高效索引问题。