基于EKR+的GML整体索引

 摘要：为满足GML数据的语义空间查询的需要，在对GML空间数据特性、传统的空间索引与XML索引分析的基础上，设计以GML地理要素为基本索引单元、联合地理要素的扩展区域编码与空间几何属性为索引关键字的GML整体索引（EKR+：Extend K-Means R+）结构与算法，并把索引在GML的语义空间查询中加以应用。最后，通过实验对比分析索引的基本性能。
 关键字：路径索引   扩展区域编码   GML整体索引   语义空间查询

Abstract: On the semantic and spatial query demand of GML data, Tap the GML data characteristics, and the traditional spatial data indexing techniques and XML data indexing analyzing, the paper designed structures and algorithms of GML holistic index (EKR+：Extend K-Means R+), which based on geographical feature units joints extended regional codes and geometric attributes for the key index, On the side, Based on EKR+ index designed the semantic and spatial join algorithm. Finally, performances study show that our techniques outperform the more traditional approach.
Keywords: Path index, Extended-regional code, GML holistic index, Semantic and Spatial Query
 
 1. 引言
 OGC(OpenGIS Consortium)推出的地理标记语言（GML：Geography Markup Language），逐渐成为地理信息共享交换以及集成等应用的编码标准。为能够从海量的GML空间数据中快速查询检索需要的信息，需要高效灵活的索引机制的支撑[1]。
 GML数据模型是完整意义（包括逻辑表达与物理存储）的面向对象数据模型。GML数据文档中不但存储地理对象的多种属性信息，还记录着地理对象之间包含关系——语义隶属信息[2、3、4、5]。目前，对GML索引主要采用彼此独立的路径索引与空间索引的处理方式。传统的空间索引技术是针对传统的分层以及拓扑关联数据模型，对地理空间对象几何属性的索引，本质上属于地理对象的多维属性值的索引；XML的路径索引方法虽然可以用于GML地理数据的语义包含关系的索引，但是现有的索引方法，均没有利用地理要素编码的区域特性。因此，只有建立两类信息的联合索引才能满足GML数据的快速的语义空间查询的需要。
 本文以GML文本文件格式数据为索引对象，设计了以GML地理要素为基本索引单元、联合地理要素的扩展区域编码与空间几何属性为索引关键字的GML整体索引（EKR+）结构；并把索引在GML的语义空间查询中加以应用，设计了基于索引的语义空间连接算法；最后通过实验对比分析索引的基本性能。
 2. GML整体索引技术实现分析
 传统的空间数据索引按搜索区域划分多维空间数据：点、面区域两类索引[6]。针对空间数据对象的特点，它们互有优缺点，其基本性能的对比如表1所示。XML路径索引的主要目的是辅助进行快速的文档结构查询即路径查询。路径索引包括：路径概要索引与路径编码索引[7]。路径结构概要索引方法的主要思想是对整个XML数据进行归纳，总结出所有出现过的标记路径以及这些标记路径可到达的节点，以实现数据索引。基于路径区域编码索引利用路径查询的分解合并的处理策略[8、9]，关键操作步骤包括：对XML文档进行区域编码；根据编码值分别建立每类元素的索引；执行路径查询，先分解复杂路径为包含两个元素关系的二元路径序列，再逐个合并二元路径以获取最后的查询结果；当XML等数据更新时，需要进行相应索引数据的更新。
 地理要素是GML文档中复杂元素类型，其空间几何属性与区域编码均为数值型数据，这是整体索引结构实现的基础：采用多维空间数据的索引方法以两类属性关键字可建立GML的整体索引结构[10]。在GML整体索引空间中，区域编码可看作是具有范围变化的1维数据，也可以看作是不具有范围变化的2维数据。根据对对象映射索引方法的分析：索引维数越多，索引空间中对象的几何形态维数越少。采用高维索引方法的优点是结构简单、更新灵活，但存在不能体现地理要素属性的连续性的缺点。当把区域编码轴看作1维时，元素之间的语义关系的判断，通过编码在1维方向的包含与邻近关系的比较实现；反之，则通过二维空间的矩形范围的拓扑关系运算实现。本文主要研究线、面多维对象数据的索引，为保持对象区域变化特性，我们采用2维的处理方式。
 把GML地理要素的扩展区域编码加入索引空间会使得空间几何对象的形态更为复杂，尤其是对多维的空间数据，因此需要GML整体索引必须能够解决维数较高的情况。通过表2的性能对比分析，基于面区域划分、采用对象分割/复制策略的索引方法比较适合，同时，考虑同目前传统空间数据库索引技术的结合，选定R+树索引作为GML整体索引的基础。
 
 表 1 传统的空间索引性能对比
 Tab.1.Performance contrast of traditional spatial indexs
 
    支持索引对象 存储空间利用率 动态更新效率 支持高维数据 查询效率 通用性
点区域划分 点 高 高 否 高 差
面区域划分 对象影射 空间对象 低 高 是 高 差
 对象界定 R树以及多维变体 空间对象 高 中 否 高 好
  R树的高维变体索引方法 空间对象 低 差 是 中 好
 对象分割/复制 空间对象 中 中 高 高 好
 3. EKR+索引
 区域编码是建立GML整体索引结构的基础，为满足GML文档动态更新的需要，通过采用编码预留的方法可以避免对GML文档中地理要素的重复编码，从而提高文档更新的效率[11、12、13]。GML应用文档通常严格按照应用模式的要求，即GML文档插入地理要素的类型、位置以及顺序都进行限制。因此，需要设计基于模式的扩展区域编码方法(Extended Region Code)。ERCode编码主要分为两个步骤：(1)计算GML文档中所有地理要素的预留编码空间（RegionSize）；(2)计算GML文档中所有地理要素的前序编码值（Pre）。
 EKR+索引结构单元信息如图1所示， head是整个索引结构的根节点，而fillfactor是每个节点包含的实体范围的最大限定值。在Node结构中包含的head是一个Cell元素，它用来存储节点包含的Cell链表的第一个Cell，而Parent存储父节点的Cell。在Cell结构中current是记录当前Cell的索引范围，而next、prev则分别存储当前Cell连接的前后Cell，child则是记录当前cell的子节点。整个索引数据结构即是通过Node与Cell的相互嵌套建立。在MBR结构中通过Rect结构存储当前实体的范围闭包。 Rect结构中的low与high数组，分别存储闭包范围的左下与右上角的坐标值（X1、Y1、Z1、P1；X2、Y2、Z2、P2）。P1、P2是对ERCode区域编码（Pre，RegionSize）的改造：P1等于前序编码（Pre），而P2等于前序编码值（Pre）加上预留的区域编码空间（RegionSize），即P2=Pre+RegionSize。GML中地理要素之间语义关系通过P值的比较进行判断。
 选定R+树为索引作为GML整体索引的基础，必须解决其在节点分裂时过渡的向上向下分裂运算，出现分裂的“死锁”的问题[14、15]。通过使用K-Means多路聚类分区[16]方法，改原来在R+节点分裂时的二路分区为多路分区，充分挖掘实体范围的空间聚类特性，减少实体范围切割数情况，减少向下分裂次数。K-Means聚类分区算法应用GML整体索引的节点分裂主要包括以下3个步骤：（1）循环遍历2~（node.count-1）个聚类点的聚类方法序列中的最优解；（2）求解指定聚类节点个数后的多种聚类方法的最优代价；（3）评价每种聚类方法的分裂代价。在聚类分区的过程中，为了充分挖掘空间索引实体的空间分布特性，分区的过程中，为了充分挖掘空间索引实体的空间分布特性，范围分区并不一定按照一个轴进行，可以分别按照X、Y、Z、P轴混合交叉进行，如图2所示。
 决定实体范围聚类分区方式优劣主要考虑三个因素：几何特性、实体范围切割数以及聚类分区个数。几何特性是聚类后形成新的实体范围与原有聚类实体范围集合的最大闭包的比值，比值越小聚类效果越好，反之则越差。同样，实体范围切割数越小，效果越好，反之则越差。聚类分区个数（K）也是体现索引性能的重要指标，K值越小索引性能越好，反之则差。实体范围切割数与几何特性具有一致的索引性能，而他们与聚类分区个数反映的索引特性恰好相反。例如：K等于聚类实体范围集合的个数（即在公式1中，选定k=n）时，就失去了索引的意义。利用简单的加权计算方法得到聚类分区结果的评价公式1。

KMS聚类分区算法改原来R+树中的二路分裂为多路（K）分裂方式，这样会使父节点的实体范围个数更容易超标（M），加大向上分裂的概率。为此需要对其父节点的M值依照公式2，进行动态调整。调整只在满足f>0的情况下进行，即父节点的限值减去父节点的当前实体范围数（除去当前的分裂的节点）以及子节点的平均分裂节点数后的差值。，
其中，n是聚类分区的实体范围个数，Smax是聚类分区后的最大闭包空间，
Countmax是聚类分区最大切割实体范围的个数，k是聚类分区后形成的节点的个数，分别是三个评价因子的权值。 公式1
 公式2

 4． 基于索引的语义空间的连接运算（IS-SJQ：Index-based Semantic Spatial Join Query）
 连接运算是GML查询分析的基础，基于GML整体索引能够提高语义空间连接运算的效率。传统的空间连接只对地理要素的几何拓扑关系的运算，其并没有考虑地理要素的语义关系的限制。但是，GML地理数据的语义空间连接要求，同时进行空间几何拓扑关系与语义包含关系的运算。索引树中索引节点实体闭包范围是按照空间包含的关系建立，在进行语义连接运算的过程中，可以进行剪枝运算。以相交语义连接运算为例算法设计如下：
 算法SeqListNode * IS-SJQ _ Intersect（Node A，D；MBR rect）
 输入参数：相交语义连接的索引结构树的根节点，A：代表祖先（父亲）索引树的根节点，D：代表子孙（儿子）索引树的根节点。Rect代表节点A与D的实体范围的交集。假定两颗索引树有同样高度。
 输出结果：满足相交语义连接关系的实体范围链表。
 方法：采用广度优先的方法对两棵索引树同步遍历，逐层比较实体的空间以及语义相交关系（对于叶子节点需要进行包含关系的判断）。通过使用父节点的实体交集，能够有效减少比较实体的个数；而通过使用堆栈能够把语义连接结果排序输出。
 步骤1[获取有效实体]
  RectListNode * AList, DList;
  SeqListNode * Result=CreatNode()；
     For i=1 to A.count-1 do
   If A.i.rectrectthen
   AList.add (A.i)
  For j=1 to S.count-1 do
   If D.i.rectrect then
   DList.add (D.i)
 步骤2[排序实体范围]
  //默认按照P轴排序，
 //如果在索引的构建过程中是按照P轴聚类分区，则无需重新排序
  SortDesc（AList）；
  SortDesc（DList）；
 步骤3[输出结果]
  If A=leafnode &&D=leafnode then
   Result = Result +Stack-Tree-Desc（AList,DList）
  Else
 步骤4[递归运算]
 SeqListNode * SeqListNode =Intersects _Sweep (AList, DList);
 While SeqListNode! =null do
 If（SeqListNode.First->child! =null）&& （SeqListNode.Second->child! =null）then
 Rect= SeqListNode.First->child.RectSeqListNode.Second ->child.Rect；    IS-SJQ _ Intersect（SeqListNode.First->child, SeqListNode.Next->child,Rect）；
    SeqListNode =SeqListNode->next;
 步骤5[返回结果]
  Return Result； 
 利用堆栈的后进先出特性，算法中使用Stack-Tree-Desc可以保证连接运算的结果按照祖先后代（父子）的路径编码值排序（升序或者降序）成对输出。扫描方法（Intersects _Sweep）与堆栈排序（Stack-Tree-Desc）方法的不同之处是：前者是包含关系，而后者是相交关系。相交关系具有对称性，比较的起始顺序需要交替进行。
 5. 实验结果与结论
 实验的计算机平台为Dell4550、主频2.4GHz、内存512M、硬盘40G，系统集成开发平台JBulider2005，操作系统为Microsoft Windows XP Professional。实验采用的数据是南京市路灯GIS管理系统中的基本设备设施的空间数据，原始的数据存储格式为ESRI SDE8.3，通过利用FME2003的软件转换并语义合成GML文档数据。
 5.1. 索引构建性能分析
 为进行索引性能的对比，实现生成了R、R+以及EKR+三种类型的索引数据，其基本信息如表3所示，可以看出，基于EKR+索引生成的索引文档树的最大深度以及平均节点深度比较合理，而这是决定基于索引查询、以及动态更新性能的重要因素。各种索引的初始构造系统响应时间的对比如图3所示。可以看出EKR+索引的初始构造性能与R索引方法的性能基本相当，但明显高于R+的性能。
 表2 实验数据的基本信息    Tab.2. Information of experimental data
文件名 文件大小 分类地理要素数量
  要素类型 要素个数
Gulousb.gml 5.83M 箱式变 63
  接线井 3051
  路灯线 585
 
 
 
 
 
 
 
 表3各种索引文档的基本信息
 Tab.3. Information of Index documents
索引 文件名 文件大小（kb） 最大深度 平均扇度 叶子节点数 非叶子节点数
EKR+ EKR+_xsb.inx 8 4 4 63 16
 EKR+_xj.inx 43 6 5 3051 653
 EKR+_ldx.inx 267 5 5 585 98
R R_xsb.inx 6 4 4 63 15
 R_jxj.inx 51 7 4 3051 1080
 R_ldx.inx 234 5 5 585 98
R+ R+_xsb.inx 15 5 4 63 80
 R+_jxj.inx 68 7 4 3051 1120
 R+_ldx.inx 346 7 4 585 843

 5.2. IS-SJQ的性能分析
 在IS-SJQ运算过程中需进行空间几何拓扑与语义关系的运算，但空间几何的拓扑运算限于语义连接运算的元素之间，影响运算系统开销因素只为索引节点的个数。选取路灯线与箱式变的各种索引文件为实验数据，分析其空间拓扑空间以及语义包含的运算性能。图4是系统响应时间的实验结果对比，其中X轴为路灯线与箱式变的各种索引文件中平均节点数。

 5.3. 结论
 本文通过对GML数据特性、XML索引技术与空间索引技术特点的分析，根据GML数据语义管理的需求的需要，设计了EKR+索引算法，以及基于索引的语义空间连接算法。实验证明，本文设计的GML整体索引算法具有较高的系统性能，为GML数据的语义空间管理奠定基础。

参考文献
兰小机. GML空间数据存储索引查询机制研究[D]. 南京师范大学博士学位论文，2005.5.
张书亮. CGML空间数据互操作研究. 南京师范大学博士学位论文[D]，2004.5.
Galdos Systems Inc.GML4J. https://sourceforge.net/projects/gml4j/.
兰小机, 闾国年, 张书亮. 一种通用GML 3.0解析引擎的设计与实现[J]. 地球信息科学. 2005（1）.
M.E. de Vries etc. The GML prototype of the new TOP10 vector objects model. Technical report, December 2001 [www.gdmc.nl/relay/gist9.pdf].
陶志刚,赵敬道,谭建成.地理空间索引技术研究[J].测绘学院学报,2002,19(1):73-75.
林茂桐.XML文件之索引方法之设计制作[D].国立中山大学资讯工程学系硕士论文,2002.6
D. Srivastava, S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, and Y. Wu. Structural joins: A primitive for efficient XML query pattern matching. In ICDE, pages 141{152, February 2002.
Chun Zhang, Jeffrey Naughton, David DeWitt, Qiong Luo, and Guy Lohman. On supporting containment queries in relational database management systems. In Proceedings of the 2001 ACM-SIGMOD Conference,Santa Barbara, CA, May 2001
Michal Kr´atk´y. Multi-dimensional Approach to Indexing XML Data. Technical University of Ostrava, Czech Republic, Ph.D. Thesis, 2004.
罗道峰,孟小峰,蒋喻.XML数据扩展前序编码的更新方法[J].计算机科学,2003,30(10):99~104.
路燕,张亮,汪卫,等.一种新的XML文档编码机制[J].计算机研究与发展,2004,41(3):500~503.
张硕,李建中,王宏志,何震瀛. 基于扩展编码的在线XML文档加载机制[J], 2004,40(10):1830~1833.
Timos Sellis, Nick Roussopoulos and Christos Faloutsos. The R+-tree: A Dynamic Index for Multi-dimensional Objects, Proceedings of the 13th VLDB Conference, Brighton 1987.
Dantong Yu and Aidong Zhang. ClusterTree: Integration of Cluster Representation and Nearest Neighbor Search for Image Databases. In IEEE intemational Conference On Multimedia and Expo， New York City， July 2000.
Brakat soulas S., Pfoser D., Theodoridis Y.. Revisiting R-tree construction principles. In : Proceedings of t he 6t h ADBIS ,Bratislava , Slovakia , 2002 , 149～162.