基于分布式内存计算的空间数据近似查询处理方法

仇阿根

中国测绘科学研究院，北京 100830

基于分布式内存计算的空间数据近似查询处理方法

仇阿根

中国测绘科学研究院，北京 100830

地理数据交互式可视化与空间分析等是地理信息系统(Geographic Information System,GIS)应用的重要功能，而现有的地理空间数据库与地理数据服务标准难以满足实时数据可视化及空间分析的要求。根源在于空间数据库中地理要素的查询结果是精确、唯一的；查询时间和数据量只与要素本身相关；查询时地理要素无法根据条件动态生成。而在实际应用中，地理要素可以是近似的、变化的；查询时间和数据量可以作为查询约束条件；地理要素可以根据查询条件动态生成。

为此，本文提出以空间近似查询结果表达地理要素，即通过顶点采样实时生成要素并报告近似误差，实现查询时间和数据量的灵活控制。基于此，提出了海量空间数据集的多分辨率表达模型，设计了以分布式内存计算、顶点树型层次结构、加权广度遍历算法为基础的空间近似查询处理方法，实现了基于关系数据库的空间近似查询引擎，形成了基于空间近似查询的网络GIS架构，解决了网络GIS的交互式可视化与空间分析的功能与性能问题。具体研究内容如下：

(1) 基于分布式内存计算的空间近似查询理论。总结了近似查询与分布式计算的基础理论，根据地理要素的特点、地理数据交互式可视化与空间分析的需求，针对空间查询数据量难以有效控制的问题，定义了面向交互式可视化的空间近似查询，提出了多分辨率表达模型。通过递归细分、数据采样、应用处理、误差计算等步骤建立表达模型，并将计算密集型任务分布化，提供了误差与数据量可控的空间近似查询基础算法与数据结构。

(2) 地理要素近似误差计算与顶点层次结构构建方法。基于递归细分与误差计算的多分辨率表达模型，将地理要素数据分布式内存计算处理，建立顶点树型层次结构，形成了地理要素的多分辨率表达。面向数据可视化，将地理要素数据递归细分系数设为2，提出了地理要素顶点层次结构的构建方法与存储模型，设计实现了顾及误差条件的空间索引等。

(3) 地理要素近似查询算法。以加权广度优先算法为基础，提出了时间/数据量约束、误差约束的地理要素窗口近似查询处理算法，包括时间/数据量约束条件下树型层次结构的加权广度优先遍历，在查询过程中使用近似查询约束条件与空间范围约束条件，进行联合剪枝以提高效率的方法；在关系模型的基础上，研究查询条件与空间连接的特点运用多维索引以提高效率的方法。

(4) 地理要素顶点层次结构动态更新算法。根据地理要素连续更新的特点，提出了基于最小化代价函数的顶点层次更新算法。以关系模型下顶点层次结构为基础，研究代价最小的顶点层次结构局部更新方法，分析顶点序列的插入、删除、修改等操作的计算复杂度及I/O复杂度，研究不同的顶点层次结构构建参数对于动态化更新算法的影响。

(5) 海岸线数据实证研究。提出了基于空间近似查询引擎的网络GIS架构，开发了地理数据交互式可视化原型系统。针对OpenStreetMap海岸线数据，建立了海岸线数据的顶点层次化数据库，实现了地理要素的交互式可视化，并对试验结果进行了对比分析，验证了网络GIS架构的可行性及空间近似查询处理方法的实用性。

In-memory Distributed Computing Based Approximate Query Processing on Spatial Data

QIU A’gen

Chinese Academy of Surveying and Mapping，Beijing 100830，China

his doctoral degree from Wuhan University on June 2017，majors in government geographic information services and geospatial big data technologies.

仇阿根.基于分布式内存计算的空间数据近似查询处理方法[J].测绘学报，2017,46(12)：2044.

10.11947/j.AGCS.2017.20170602.

QIU A’gen.In-memory Distributed Computing Based Approximate Query Processing on Spatial Data[J]. Acta Geodaetica et Cartographica Sinica,2017,46(12):2044. DOI:10.11947/j.AGCS.2017.20170602.

P208

D

1001-1595(2017)12-2044-01

测绘地理信息公益性行业科研专项(201512032)；测绘地理信息公益性行业科研专项(201512027)；中国测绘科学研究院基本科研业务费(7771614)；国家重点研发计划(2016YFC0803108)

2017-10-26

仇阿根(1976—)，男，2017年6月毕业于武汉大学，获工学博士学位(指导教师：刘纪平研究员)，研究方向为政府地理信息服务与地理空间大数据技术。

E-mail：qiuag@casm.ac.cn