利用双重索引快速构建道路网络连通拓扑

路网拓扑关系的生成是进行最优路径规划的基础。本文针对ISO GDF4.0模型对道路连通拓扑的定义,结合最优路径规划对道路网络连通拓扑的要求,提出一种使用R-tree空间索引和B-tree索引双重索引方式快速生成道路连通拓扑的算法。连通拓扑快速构建算法包括新道路生成和网络拓扑提取两部分,新道路生成过程中,首先,自上而下地打断道路形成直线段集并求交点,然后,自下而上地重构直线段集以生成新道路。在打断道路求交点过程中,对道路建立R-tree空间索引,显著提高了几何要素的查找速度。在网络拓扑提取过程中对序列化数据建立B-tree索引,使得其查找速度大大加快。通过对双重索引算法的时间复杂度分析与验证表明,本文提出的拓扑生成算法具有较高的执行效率。     

基于空间网格和Hilbert R-tree的二级R-tree空间索引

针对分布式海量空间数据库管理要求，提出了一种基于空间划分网格、Hilbert R-tree和普通Rtree的二级空间索引结构，该结构被命名为H2R-tree。然后，详细讨论了该结构的优点，并给出了实现算法。实际算例表明，H2R-tree具有多方面的优良性能，是一种值得推广的二级索引技术。     

顾及多细节层次的三维R树索引扩展方法

多细节层次表达是三维GIS的重要特征之一。为提高细节层次模型的管理效率,本文提出一种扩展多细节层次功能的三维R树索引方法,通过全局优化和三维聚类分析建立动态三维R树索引,研制了先自下而上、后自上而下全局搜索的节点选择算法和基于k-medoids聚类算法的节点分裂算法,保证节点尺寸均匀、形状规则以及重叠减少。基于良好的三维树形结构,本文扩展了传统的三维R树索引结构,实现R树索引和细节层次模型的无缝集成。为验证本文方法的有效性,通过仿真实验,结果证明了本文方法能很大程度地提升多细节层次三维城市模型数据库的空间查询效率,具有较好的应用前景和实用价值。     

一种集成R树、哈希表和B*树的高效轨迹数据索引方法

为兼顾时空索引方法的空间利用率、时间效率和查询种类,提出了一种新的轨迹数据索引方法——HBSTR树。其基本思想是:轨迹采样点以轨迹节点的形式成组集中管理,哈希表用于维护移动目标的最新轨迹节点,轨迹节点满后作为叶节点插入时空R树,另外采用B*树对轨迹节点构建一维索引,既有利于提升索引创建效率,又同时满足时空条件搜索和特定目标轨迹搜索等多种查询类型。为提升时空查询效率,提出了新的时空R树评价指标和节点选择子算法改进时空R树插入算法,同时提出了一种时空R树的数据库存储方案。试验结果表明,HBSTR树在创建效率、查询效率和支持查询类型等方面综合性能优于现有方法,支持大规模实时轨迹数据库的动态更新和高效访问。     

三维GIS中R树空间索引研究

对于三维GIS来说,建立高效的三维空间数据索引是其关键技术之一。R树索引是近年来应用最广泛的方法之一。本文以覆盖面积和重叠面积之和作为R树结点插入标准,并且引入K均值聚类算法对结点分裂算法进行了改进。另外,对于三维GIS中较大的地物如道路、河流等,实施裁剪策略。从而使R树同层结点间的重叠度显著下降,空间对象的聚簇也更趋合理,有效提高了三维GIS数据库的查询速度。     

并行R树空间索引中叶节点大小的确定方法研究

并行R树空间索引结构中叶节点的大小是影响索引效率的主要因素,其确定方法是并行R树索引结构性能优劣的关键。本文讨论并设计了一种多层并行R树空间索引结构,文中以系统的查询响应时间作为性能评估指标,给出了并行R树叶节点大小的确定方法,并通过实验验证了该方法的有效性和适用性,同时也论证了本文所设计的多层并行R树索引结构是合理的和高效的。     

一种结合R树索引和海伦公式的偏航算法

针对卫星导航系统中嵌入式终端常用偏航算法(欧氏距离度量法和缓冲区近似法)的局限性,提出了一种结合R树索引和海伦公式的改进偏航算法。该算法采用R树索引筛选法缩小目标点所在航线范围,结合海伦公式快速计算出目标点到航线的距离,进而做出偏航判断。理论分析和实验结果表明,改进算法实现零误差快速偏航判断,显著提高导航定位终端偏航报警的实时性和准确性,从而降低了对终端计算能力的要求,满足了上万个航路点的快速偏航计算要求。     

基于Ex-Dewey前缀编码与R树的GML空间数据索引机制

大量GML空间数据的出现,使其有效性的查询处理面临严峻挑战。索引技术是决定数据查询性能的重要因素之一。鉴于GML空间数据XML格式编码的特点,为充分利用Dewey前缀编码方案并消除原方案中节点的插入、删除影响其后趋同胞节点及其子孙节点编码的变更等缺点,论文提出了一种扩展的Dewey编码方案--Ex-Dewey,用以实现对GML文档数据的整体编码和非空间数据的索引构建。研究给出了Ex-Dewey前缀编码的GML非空间数据索引构成模式与处理策略;结合Ex-Dewey,提出GML空间数据索引基于R树的构建,给出了索引构成模式与处理策略。GML空间与非空间数据索引构建,既独立又紧密关联,共同实现GML空间数据的索引。该索引机制意在用于原生GML空间数据库索引构建或单纯GML文档集索引构建中。