论文部分内容阅读
由于应用需求的驱动，以及基础科学技术、网络基础设施的快速发展，地理空间信息技术正在进入新的发展阶段。地理空间信息技术发展新阶段的特点突出表现在面向因特网和移动互联网的公众级应用，空间信息的广泛共享，空间信息服务的蓬勃发展及其广泛互操作等等。各类地理空间信息服务之间的互操作及与客户端应用之间的交互，将产生越来越多的动态地理空间数据，而对动态地理空间数据的即时处理效率将严重影响地理空间信息服务及客户端应用的性能。
本文以GML作为动态地理空间数据的描述格式，研究解决GML即时查询处理中的效率瓶颈问题。本文定义了GML即时查询语言，设计了GML即时查询套件GIOTk作为后续研究的实验平台，针对内存处理模式和流处理模式分别提出GML即时查询算法，并分别从解析模型和编码方式的角度进行优化，根据算法研究实现了即时查询套件GIQTk的各个组件，并探索了本文研究成果的应用模式。在以上几个方面，本文主要取得了以下创新性成果：
1)内置空间数据类型和空间运算符的GML即时查询语言
查询语言是进行查询处理研究的基础。针对GML的结构特点，本文基于XPath的路径导航机制提出GML即时查询语言SITPath。通过继承标准运算符，SITPath支持非空间属性查询条件的构造；同时增加了空间扩展，允许根据空间属性条件和非空间属性条件完成组合查询。SITPath的空间扩展包括节点检测时对空间数据类型的缺省支持(以简单要素模型为代表)，定义基本空间信息运算符、空间关系运算符、空间分析运算符三类空间运算符，并通过扩展运算符接口支持与标准运算符的嵌套以及空间对象的手工输入。另外，针对流模式单次遍历顺序访问的限制，从动态地理空间数据查询处理的实际需求出发，定义了流模式支持的SITPath语言子集，在支持丰富的语言特性与实现高效的求值算法之间取得了较好的平衡。
2)基于查询表达式结果缓存表的内存模式即时查询
内存处理模式适用于需要实现丰富查询语言特性并且具有充足可用计算资源的情形，但可处理数据量受限于计算资源。基于内存模式，本文提出了支持完整SITPath语言的即时查询求值算法。通过在GML文档节点上挂接查询表达式片断的求值结果缓存列表，消除了基本求值算法由于大量重复计算带来的指数级复杂度。同时通过在空间数据元素节点上挂接空间对象缓存，避免了空间对象的重复构造。在该算法基础上，本文实现了GIQTk套件中的内存模式GML即时查询引擎组件MQE。理论和实验证明，查询表达式结果缓存表和空间对象缓存显著提高了内存模式SITPath查询求值算法的时间效率，但空间效率不够理想。
3)基于GML非抽取解析模型的内存模式即时查询优化
为了突破内存处理模式的局限性和解决缓存表方法带来的内存消耗问题，本文深入分析了由解析方式造成的内存模式处理效率低下的根源。从改变解析方式和精简数据结构的角度，本文基于非抽取解析方法设计了GML优化解析模型，并利用新解析模型对内存模式即时查询求值算法和内存模式GML即时查询引擎组件MQE完成了进一步优化。对比实验证明，GML优化解析模型大幅提高了内存模式下GML即时查询处理的时空效率，使得相同计算资源条件下能够处理更大的动态地理空间数据量。
4)基于TreeStack查询机模型的流模式即时查询
流处理模式适用于可用计算资源有限或待处理动态地理空间数据量过大的情形，但由于对数据访问方式的严格限制，难以支持丰富的查询语言特性。本文提出由多棵树构成的TreeStack查询机模型，并设计了通过一次遍历SITPath查询解析树即可完成的查询机构造算法。在TreeStack查询机模型基础上，本文设计了流模式即时查询求值算法，主要包括基于TraceStack运行时栈的激活匹配过程和基于谓词状态数组的谓词计算过程，并实现了GIQTk套件中的文本GML数据流即时查询引擎组件SQE-T。算法复杂度分析和对比实验证明，本文提出的查询机模型和查询求值算法与当前基于自动机模型的查询算法相比具有更好的时空效率。
5)基于EXI编码的流模式即时查询优化
为了解决文本GML编码冗余问题，进一步优化流模式即时查询处理，本文提出用EXI编码提高GML数据流的编码效率。本文分析了EXI编码的特点及其适于作为GML高效编码的原因，设计了支持空间数据类型优化的EXI编解码算法，实现了GIQTk套件中的EXI编解码处理器组件EEP和EDP。本文将TreeStack查询机模型和TraceStack求值算法应用于EXI编码GML数据流，提出EXI解码与查询求值同步的算法框架，实现了GIQTk套件中的EXI编码GML数据流即时查询引擎组件SQE-E。对比实验证明，EXI编码能够显著降低GML数据冗余，并且显著提高流模式即时查询处理的时空效率。