空间索引技术及其GIS应用综述

空间索引技术可提供高效的空间数据组织与管理方式,以支撑海量空间数据的挖掘与分析。针对当前空间索引存在的知识体系不明晰、选择难等问题,该文通过文献调查法和CiteSpace工具,依据空间划分及映射方法将空间索引划分为基于树结构、格网、空间填充曲线和地址编码的空间索引四大类,并综述其原理、空间结构、适用范围及在GIS领域的应用,最后对空间索引在数据组织、高效计算、可视化、可靠性等方面的研究进行展望。结论如下:基于树结构的空间索引最具普适性且可以处理多维度及多层次的数据,查询性能依赖于树结构的平衡性及数据的分布;基于格网的空间索引可以均匀划分空间以便于高效范围查询,却不适用于非结构化或动态数据集;基于空间填充曲线的空间索引可以在实现维度压缩的同时保持局部邻近性,但插入或删除数据可能导致整个曲线的重构难以频繁更新;基于地址编码的空间索引将语义地址信息转化为编码信息,便于高效检索,然而语义地址匹配仍存在较大误差和不确定性。研究结果可为空间数据组织和结构设计提供参考。

一种网格化高并发Skyline查询处理方法

为减少冗余支配测试对Skyline查询性能的影响并提高Skyline查询处理的效率,本文将测试单位扩大为网格,并设计了一种基于网格分层划分的Skyline查询方法.通过不断缩小Skyline点集所在网格的方式,使网格之间的支配关系与点支配关系重合,从而避免了点与点之间大量无效的支配测试,提升了Skyline查询处理的效率.方法中同一层的网格可并行计算,且层次计算过程可达到任意精度,适用于计算能力有限但对结果精度要求不高的场合.实验结果表明,方法与现有Skyline查询处理方式相比具有数据吞吐量大、响应速度快等特点,在拥有高性能GPU或多核CPU等高并发环境下其优势更为明显.

基于多源遥感数据的人口空间网格化研究——以福州市为例

利用GIS(地理信息系统)并应用多源遥感数据等对福州市人口空间网格化进行研究。以福州市人口、地理基础信息数据为基础,提取DMSP/OLS夜间灯光数据以及NDVI(归一化植被覆盖指数)数据建立人居指数模型,并根据模型进行人口空间分布模拟,叠加高程数据对模型进行修正。结果表明:夜间灯光遥感影像与人口分布具有强相关性;NDVI与夜间灯光值结合可以解决夜间灯光像元溢出问题,提高数据空间化的质量和精确性。利用DMSP/OLS数据与NDVI数据构建的人居指数模型作为遥感数据与人口数据之间的纽带,对实现人口空间网格的展布起到了关键的作用。

基于分块分层网格索引的电网出图性能优化分析

阐述电网空间数据的模型特点和自定义显示规则,提出按设备类型进行分块、按电压等级进行分层的网格索引技术,在提高电网出图性能上的优势。

基于M2SFCA的普惠性幼儿园空间可达性分析--以合肥市包河区为例

在针对“多胎”政策开放、加强公共资源适儿化、普惠化建设的社会发展背景下,提出基于人口空间格网的改进两步移动搜索法,对城镇普惠性幼儿园的空间分布进行研究.以合肥市包河区为例,街道为研究层级,把可达性与CDI指数结合起来评价普惠性幼儿园空间资源分配的均衡性,并通过ArcGIS可视化.研究表明,包河区普惠性幼儿园存在分布不均现象:一个街道存在双重优势;三个街道处于双重劣势;其余街道均存在一种劣势情况.改进两步移动搜索法与CDI指标的综合分析不仅更加有效地发现空间劣势区域,还增强了普惠性幼儿园空间可达性分析的精确度.

基于非均匀多级网格索引的矢量地图叠加分析算法

矢量地图叠加分析在实际场景使用中经常需要处理各种大规模复杂空间数据,因此算法整体分析效率的提升尤其重要。该文重点针对较大多边形对象和大量较小多边形对象的叠加分析使用场景,提出了一种有较强针对性的基于非均匀多级网格索引的矢量地图叠加分析(Non-uniform Multi-level Grid Index Overlay,NMGIO)算法,包括索引构建、网格过滤、叠加计算、拓扑构面4个步骤,通过对待分析数据集和叠加对象双向建立非均匀多级网格索引,利用数据的空间分布特点从根本上提升叠加分析效率。同时给出了算法整体时间复杂度和由C语言实现的原型系统叠加分析效果验证。

基于空间索引的规则格网DTM内插算法研究

从离散点内插规则格网数字地形模型 (DTM)方法的关键是如何提高待插点周围数据的搜索效率。该文针对离散点的空间分布特性 ,给出了基于网格分块和KD -Tree两种空间索引技术的规则格网内插方法。实验表明 ,这两种索引方法能显著提高搜索速度 ,算法内插效率较高。最后 ,在算法效率分析的基础上 ,对两种索引方法所适应的条件进行了讨论。

基于文件与基于数据库的格网索引

对建立文件和数据库支持下的格网型空间索引的关键技术及具体实现进行了详细说明 ,并通过建立实验系统 ,分别对基于文件和数据库情况下建立索引前后图形操作和目标查询的速度进行了测定、比较 ,证明了建立索引能够有效提高空间操作效率。

一种改进的自适应层次网格空间索引查询算法

海量空间数据的处理需要通过空间索引来提高效率。文章在深入研究层次网格空间索引技术的基础上,提出了一种基于内外块算法的层次网格空间索引查询算法,并结合已实现的SircGIS.NET系统,分析了它的性能,结果表明该算法大大地提高了层次网格空间索引的效率。

一种改进的网格索引生成方法

分析了网格索引的优缺点以及Bresenham等方法用于线状目标网格索引生成存在的问题,在此基础上提出了一种改进的网格索引生成方法,此方法避免了在生成网格索引时遗漏目标覆盖的网格格子,并可提高选择目标的精度。

自动调配的层次网格空间索引技术

海量空间数据的处理需要通过空间索引来提高效率。在深入研究网格类空间索引技术的基础上,针对层次网格空间索引进行若干的改进,提出了有创造性的基于正态分布的第一层网格长宽自动调配算法和完全包含的重新定义算法,并分析了它们的性能。结果表明,改进的层次网格空间索引大大提高了索引的效率和自适应的能力。

环首都圈植被分布与可吸入颗粒物的空间相关性

为了分析空气中可吸入颗粒物含量与植被覆盖间的关系，进而为减轻雾霾污染提供依据和参考，该文立足于环首都地区的环境污染程度，对环首都地区的空气可吸入颗粒物进行了相关的研究和分析，建立以环首都地区100 km为单位的圈层，并对该圈层下植被、土壤、环境、地形等重要因子按照不同矩形格网尺度进行划分，并取格网中心点作为研究点。并以环首都地区2013年的植被分布特点和规律为基础，按照矩形格网法通过地统计学Moran’s I法结合SPSS软件非线性回归分析植被分布与空气中可吸入颗粒物浓度间随距离变化的关系。经过 Moran’s 指数法分析得出环首都地区植被分布与可吸入颗粒物间随着格网尺度的增大而自相关性降低，植被盖度的自相关影响范围是6620～7131 m，可吸入颗粒物自相关影响范围是2998～6864 m。通过SPSS软件的非线性回归分析得出植被分布与可吸入颗粒物间的空间相关性影响距离是41.87 km，标准误差P均在0.001～0.003之间，相关系数R2均在80%以上，非线性回归模型拟合较好，更好的说明了环首都地区植被分布与环境污染间的空间相关关系，为日后对其他地区的植被与环境污染指数的相关性分析的研究提供了理论依据。

一种基于网格索引的空间连接查询处理优化算法

针对云环境下的空间数据连接查询处理问题,提出一种基于MapReduce框架的高效空间连接查询处理优化算法.该算法采用网格划分方法将数据空间划分成大小相同的网格单元,并将其中一类数据集中的每个空间对象,按照其中心点的位置划分到所在的网格单元中,从而避免了连接对象的复制,网格单元之间根据其所包含数据对象的交叠关系构建网格索引;对另一类数据集中的对象,仅将其复制到与网格单元中数据有交叠的网格单元,从而过滤掉不可能有连接结果的数据对象,大大减少了后续的连接计算代价.合成数据和真实数据集上的大量实验表明,本文提出的空间数据连接查询处理优化算法在性能上明显优于原有SJMR查询处理算法.

一种改进的等高线断点连接方法

介绍了几种现有的等高线断点连接方法,并在最小点对法的基础上提出了一种改进的断点连接方法。此方法在判断断点间距离大小之前先对等高线进行预处理,即将各条目标等高线自动赋予不同的颜色值,然后将图幅进行格网划分,在不同网格内搜索断点,根据颜色的差异及距离的远近自动进行等高线连接。此方法连接的准确率高于一般的断点连接方法。

基于固定网格划分和面向类对象的四分树空间索引机制

本文针对地理信息系统中的空间对象形状的不规则性和空间查询区域的不规则性，提出了一种基于固定网格划分的四分树空间索引机制，称之为ＣＥＬＬＱＴＲＥＥ。为了有效地减少空间查询的检索操作的范围，引入了面向类对象的二级查询技术，有效地提高了地理信息系统ＧＩＳ（ＧｅｏｇｒａｐｈｉｃＩｎｆｏｒｍａｔｉｏｎＳｙｓｔｅｍ）应用系统的性能。文章详细地讨论了它的空间索引机制、面向类对象的空间信息的查询、数据结构。

一种GIS自适应层次网格空间索引算法

分析了目前常用的空间索引算法的缺点,对应用最为广泛的网格空间索引数据结构进行了剖析;在描述了网格空间索引算法的同时,依据空间实体外接矩形的几何特性,给出了具有自适应能力的改进型网格空间索引算法———自适应层次网格空间索引算法;最后分析了此算法的自适应性和索引效率。

一种基于道路网络拓扑改进的格网空间索引算法

按照规则格网进行索引时需要对跨格网的道路进行分割并维护相关的复杂关系(比如道路与交通规则,方向看板,车道连接之间的关系等),算法实现难度较高且会显著增加道路连接的结点数目,从而增加路径规划计算的量而影响性能.介绍了一种改进的格网索引算法,不需要分割跨规则格网的道路网络,而是根据道路网络中特定的连接拓扑关系(道路与结点之间的关系)对结点进行索引从而达到对道路的索引.

自适应双层网格的空间索引研究

空间数据索引是GIS系统中的关键技术,针对目前主流的网格空间索引方法进行了充分的研究比较,指出了网格索引方法对空间要素进行索引是高效的,但对于非规则地图它是不适应的。在此基础上设计了一种新的空间索引的方法,即自适应双层网格索引。详细地介绍了这种模型的实现过程,并且用实验充分论证了这个模型的效率,认为利用自适应双层网格索引检索空间数据时,处理、查询效率和占用空间等各方面具有较大优势。

空间索引的新机制——G树

研制空间数据库管理系统，提出一种Ｇ树的空间模型和动态格网的操作算法，设计实现了基于页面的新的空间索引机制，有效的解决了Ｎ维空间数据的索引问题．

紧致的Hilbert曲线Gray码索引算法

Hilbert曲线具有良好的聚簇性,使其成为设计全球立体网格多维数据索引的重要工具。但当数据集在不同维度上的分布密度存在较大差异时,常规Hilbert曲线索引会出现大量的冗余。对此,本文基于Gray码推导分析了Hilbert曲线索引的构造特点,进而设计实现了紧致Hilbert曲线索引算法,在保持Hilbert曲线良好聚簇性的同时,避免了数据维度分布差异带来的索引冗余问题。试验结果表明,相比常规Hilbert索引,紧致Hilbert曲线索引计算复杂度相当,在实例数据测试中编码耗时减少约40%,索引存储空间减少约46%,排序速度约为Hilbert排序的4.3倍。