面向空间索引优化的空间对象近似方法研究

发布时间：2020-06-07 06:37

【摘要】：空间索引是依据空间对象的位置和形状或空间对象之间的某种空间关系按一定顺序排列的一种数据结构,旨在快速筛选与特定空间操作无关的空间对象,是确保高效搜索和展示空间数据效率的重要指标,其性能的优劣直接影响地理信息系统与空间数据库的整体性能。目前,国内外涌现出各类空间索引结构,尽管他们从不同角度对空间索引算法进行了优化,但仍存在很大的局限性。其中,在索引树结构方面,节点间较高的空间重叠度,造成索引树深度的增加、同一空间查询出现多条查询路径等一系列弊端,从而降低了空间索引质量,影响空间索引性能。而且随着数据量和数据类型复杂程度的剧增以及索引数据的不断更新,这类弊端也愈发明显。空间对象近似(SpatialObjectApproximation)精度较低,是导致索引节点间较大重叠度的一个重要问题。通过使用相关空间目标近似技术(如最小外接矩形)可减少原始空间目标复杂的空间关系计算,从而提高空间查询效率。地理信息系统处理的空间目标具有不规则的几何形状(如道路、河流等),若直接利用其精确空间位置来实现某些给定的空间操作(如相交、包含等),计算量会急剧增加。但现有方法未挖掘空间目标的几何形态特征,导致索引节点间存在较高的空间重叠度,进而影响空间查询性能的提升。针对上述问题,本文以优化空间索引结构为目标,从空间目标近似技术出发,结合线、面地理矢量要素的几何形态特征,提出了基于几何模板(Geometric Template)近似的空间索引优化方法,其中几何模板是指以栅格方式对原始几何对象进行粗略近似的图形。并设计相关空间数据检索实验,实验表明了该空间索引优化方法明显提高了窗口查询与空间连接查询效率与精度。本文具体研究内容与成果如下:(1)面向二维空间索引优化的几何模板针对空间对象近似精度不高、难以平衡索引树构建效率及空间复杂度等的问题,本文提出了基于多级网格剖分的几何模板构建方案。定义了以网格数据结构为基础的几何模板结构,设计了基于改进最小编辑距离和几何模板频率直方图的归类算法、基于图形字典的几何模板位编码算法以及基于位操作和几何模板空间关系预取的混合机制下的空间关系粗计算策略。(2)基于几何模板近似的空间索引优化方法鉴于R*树是R-树变体中应用最为广泛的一类,本文以R*树为例,提出了基于几何模板近似的空间索引优化方法,旨在将几何模板替换R*树中的最小外接矩形,以达到优化的目的。通过对比分析基于几何模板近似和基于最小外接矩形近似下空间索引数据构建、删除、窗口查询和空间连接查询以及节点分裂等算法的差异性。本文提出了基于几何模板空间关系粗计算的窗口查询与空间连接查询详细算法。设计了基于几何模板变换(起点变换、级别变换)和位运算的节点分裂算法,构造了基于几何模板类型和级别的面积、周长计算方法,以此为基础,最终提出了基于几何模板近似的空间索引构建和删除算法。(3)设计原型系统进行实验验证通过选择中国区域内有代表性的线和面状OSM(Open Street Map)矢量数据集,本文构建了 VGIS原型系统,从窗口查询效率、精度和存储空间压缩比方面,对提出的基于几何模板近似的空间索引优化方法进行实验分析。结果表明,基于几何模板近似的空间索引优化方法以增加少量建树时间,换取更少的窗口查询与空间连接查询时间以及存储空间占用量,提高了空间查询性能和空间利用率,且扩展了查询谓词。
【图文】：

流程图,空间检索,目标,流程

Ｒ－Ｆｉｌｅ邋（Ｈｕｔｆｌｅｓｚ邋ｅｔａｌ．，１９９０）、ＭｕｌｔｉＬａｙｅｒ邋Ｇｒｉｄ邋Ｆｉｌｅ邋（Ｓｉｘ邋ｅｔ邋ａｌ．，１９８８）、网格索引逡逑（ＧＵｎｔｈｅｒｅｔａｌ．，１９８９；胡久乡等，２００２）。此类索引在进行空间检索时，首先计算逡逑出查询对象所在的网格，然后在候选网格中快速查询空间目标。如图１－１所示。逡逑Ｒ标映射技术逦目标复制技术逦目标近似技术逦基于分层技术逡逑！点对笔更高丨丨逦°逦Ｉ：逦最小外丨丨逦罕ｔａｔＪｃ逡逑；＇——晙邋Ａ点邋｜丨丨邋｜Ｔ｜７｜逦：：邋＾邋Ａ邋＾邋ｈｉ邋ｒＭ逦；逡逑ＩＥ｝－逦５逦ｌ：ｉ邋Ｓ邋—士邋ｉ逡逑：区｝＾邋ＩＩ逦Ｙ３ＤＨ一邋基本网格邋ｉ逡逑Ｉ逦逦逦逦—逦逦１＿逦—逦逦－逡逑图ｉ－ｉ空间索引分类逡逑目前，众多国内外研究学者针对各类空间索引的不足，从不同角度提出了一逡逑些改进策略，主要包括：在空间划分方面，一方面引入了空间聚类方法如！＾逡逑ＭＥＡＮ邋（Ｋａｎｕｎｇｏｅｔａｌ．，２００２）及其改进结构（胡伟，２００３）、Ｃｈａｍｅｌｅｏｎ邋（Ｋａｒｙｐｉｓ逡逑ｅｔ邋ａｌ．，邋２００２）、Ａｌｅｘ邋（Ｒｏｄｒｉｇｕｅｚ邋ｅｔ邋ａｌ．，２０１４）等以及邋Ｖｏｒｏｎｏｉ邋（周培德，１９９９），代逡逑表的有聚类Ｒ－树（黄继先，２００５；余冬梅，２０１２；崔环宇，，２０１６）、ＨＣＲ索引（黄继逡逑先，２００６）、ＰａｔｔｅｒｎＬｉｓｔ邋（崔登吉，２０１６）等，另一方面，从空间分布模式角度出发，逡逑针对不同分布模式米用不同处理策略，代表的有Ｐａｔｔｅｒｎ－ｔｒｅｅ空间索引（吴明光，逡逑２０１５）；在空间目标近似方面

处理流程图,空间连接,处理流程

可以有效地提高空间操作的速度和效率。因此，针对无空间索引支持的连接操作逡逑难以满足应用需求，本文将不予讨论。逡逑空间连接与其他空间查询相同，通常分为两部分：过滤和求精，如图１－３所逡逑／Ｊｎ邋0逡逑｜逦逡逑Ｍ邋选祺邋ｊ－—ｊ（Ｔ）逡逑ｄＤ７＾．邋Ｌ＿逦逡逑图１－３空间连接处理流程（Ｂｒｉｎｋｈｏｆｆｅｔａｌ．，邋１９９４）逡逑如图１－３所示，ＢｒｉｎｋｈｏｆｆＴ．等人提出的空间连接的三步体系主要分为三个步逡逑骤（Ｂｒｉｎｋｈｏｆｆ邋ｅｔ邋ａｌ．，１９９４）。逡逑（１）
【学位授予单位】：南京师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：P208

【参考文献】