《测绘学报》
构建与学术的桥梁 拉近与权威的距离
基于分布式内存计算的空间数据近似查询处理方法
仇阿根
中国测绘科学研究院, 北京 100830
收稿日期：2017-10-26
基金项目：测绘地理信息公益性行业科研专项（201512032）；测绘地理信息公益性行业科研专项（201512027）；中国测绘科学研究院基本科研业务费（7771614）；国家重点研发计划（2016YFC0803108）
第一作者简介：仇阿根(1976-), 男, 2017年6月毕业于武汉大学, 获工学博士学位(指导教师:刘纪平研究员), 研究方向为政府地理信息服务与地理空间大数据技术。E-mail:qiuag@casm.ac.cn
In-memory Distributed Computing Based Approximate Query Processing on Spatial Data
QIU A'gen
地理数据交互式可视化与空间分析等是地理信息系统(Geographic Information System, GIS)应用的重要功能，而现有的地理空间数据库与地理数据服务标准难以满足实时数据可视化及空间分析的要求。根源在于空间数据库中地理要素的查询结果是精确、唯一的；查询时间和数据量只与要素本身相关；查询时地理要素无法根据条件动态生成。而在实际应用中，地理要素可以是近似的、变化的；查询时间和数据量可以作为查询约束条件；地理要素可以根据查询条件动态生成。
为此，本文提出以空间近似查询结果表达地理要素，即通过顶点采样实时生成要素并报告近似误差，实现查询时间和数据量的灵活控制。基于此，提出了海量空间数据集的多分辨率表达模型，设计了以分布式内存计算、顶点树型层次结构、加权广度遍历算法为基础的空间近似查询处理方法，实现了基于关系数据库的空间近似查询引擎，形成了基于空间近似查询的网络GIS架构，解决了网络GIS的交互式可视化与空间分析的功能与性能问题。具体研究内容如下：
(1) 基于分布式内存计算的空间近似查询理论。总结了近似查询与分布式计算的基础理论，根据地理要素的特点、地理数据交互式可视化与空间分析的需求，针对空间查询数据量难以有效控制的问题，定义了面向交互式可视化的空间近似查询，提出了多分辨率表达模型。通过递归细分、数据采样、应用处理、误差计算等步骤建立表达模型，并将计算密集型任务分布化，提供了误差与数据量可控的空间近似查询基础算法与数据结构。
(2) 地理要素近似误差计算与顶点层次结构构建方法。基于递归细分与误差计算的多分辨率表达模型，将地理要素数据分布式内存计算处理，建立顶点树型层次结构，形成了地理要素的多分辨率表达。面向数据可视化，将地理要素数据递归细分系数设为2，提出了地理要素顶点层次结构的构建方法与存储模型，设计实现了顾及误差条件的空间索引等。
(3) 地理要素近似查询算法。以加权广度优先算法为基础，提出了时间/数据量约束、误差约束的地理要素窗口近似查询处理算法，包括时间/数据量约束条件下树型层次结构的加权广度优先遍历，在查询过程中使用近似查询约束条件与空间范围约束条件，进行联合剪枝以提高效率的方法；在关系模型的基础上，研究查询条件与空间连接的特点运用多维索引以提高效率的方法。
(4) 地理要素顶点层次结构动态更新算法。根据地理要素连续更新的特点，提出了基于最小化代价函数的顶点层次更新算法。以关系模型下顶点层次结构为基础，研究代价最小的顶点层次结构局部更新方法，分析顶点序列的插入、删除、修改等操作的计算复杂度及I/O复杂度，研究不同的顶点层次结构构建参数对于动态化更新算法的影响。
(5) 海岸线数据实证研究。提出了基于空间近似查询引擎的网络GIS架构，开发了地理数据交互式可视化原型系统。针对OpenStreetMap海岸线数据，建立了海岸线数据的顶点层次化数据库，实现了地理要素的交互式可视化，并对试验结果进行了对比分析，验证了网络GIS架构的可行性及空间近似查询处理方法的实用性。
【引文格式】仇阿根。基于分布式内存计算的空间数据近似查询处理方法[J]. 测绘学报，2017，46(12)：2044-2044. DOI: 10.11947/j.AGCS.2017.20170602
8个地球的科学冷知识颠覆你的世界观！
适合所有研究生读的好文：阳光温热 科研静好
世界上最有趣最冷门的地图，刷新你的世界观！
黄昕：当你动笔，成败已定——来自IEEE评审专家的体会与思考
这个遥感学科的排名比较全，值得分享！
院士论坛| 高俊：图到用时方恨少, 重绘河山待后生——《测绘学报》60年纪念与前瞻
武汉大学老师推出最美赏樱专题地图
学术前沿| 李广云：精密工程测量技术及其发展
SCI收录的中文期刊有哪些？
权威 | 专业 | 学术 | 前沿
微信投稿邮箱 | song_qi_fan@163.com
微信公众号中搜索「测绘学报」，关注我们，长按上图二维码，关注学术前沿动态。
欢迎加入《测绘学报》作者QQ群： 297834524
进群请备注：姓名+单位+稿件编号