基于N-KD树的空间点数据分组算法.pdfVIP

第17卷 第1期 Vol. 17, No.1 2015 年1月 Jan., 2015 基于N-KD 树的空间点数据分组算法 1,2 2* 1,2 2 2 1,2 魏海涛 ，杜云艳 ，任浩玮 ，刘 张 ，易嘉伟 ，许开辉 (1. 山东科技大学测绘科学与工程学院，青岛266510 ； 2. 中国科学院地理科学与资源研究所资源与环境信息系统国家重点实验室，北京 100101) 摘要：随着科学技术的进步，地理空间数据的分析处理面临着数据量膨胀和计算量高速增长的双重挑战，为了解决 海量数据处理速度慢的问题，本文针对空间分布不均匀的点数据，从数据并行的角度，以保持数据的空间邻近性及 保证数据分组后各组数据量负载均衡为目标，提出基于N-KD 树（Number-K Dimension Tree ）数据动态分组的方 法，其是一种面向实时变化（数据量和数据空间范围变化）的空间数据动态分组方法。该方法借鉴K-D 树的创建和 最临近点有哪些信誉好的足球投注网站的思想，通过方差判断数据分布稀疏程度，利用最临近点有哪些信誉好的足球投注网站方法处理边界点，实现空间范围的不均 等切分，保证数据分组后各组数据量基本均衡。试验表明，该方法具有较好的动态分组效果与较高的计算效率；支 持各种分布状态的空间点数据的分组；分组后各组数据量负载均衡；分组算法本身有支持并行、支持分布式协同工 作模式的特点。 关键词：点数据；离散性；N-KD 树；K-D 树；动态分组；数据并行 DOI:10.3724/SP.J. 1047.2015.00001 1 引言 从而减少其空间计算所需的时间，最大限度地提高 [11] 计算效率 。目前，空间分组的方法主要有：（1）网 空间点数据集是GIS （Geographic Information 格分割法，即对数据按照地理空间范围（经纬度坐 System）空间分析中常见的数据对象之一，例如，利 标）进行等分，实现对空间点数据的分组，该方法可 用空间点集构建DEM ，空间点数据的等值线生成， 保持空间数据集的空间邻近性，简单易实现，但由 利用空间点集构建三角网等数据分析与数据处理 于数据分布不均匀，上述方法会造成各组数据的数 [1-6] 据量失衡，导致整体时间效率低下；（2 ）Lee 等人提 均涉及到空间点数据集 。然而，随着空间点数据 [12] 量的增大，串行计算对空间点数据的处理效率很难 出单向划分法 ，即仅仅按照空间数据的某个坐标 满足实际应用的要求。为了提高大数据量空间数 轴统计数据量，对数据进行等量分组，该方法同样 据计算效率，目前常用的方法是将空间点集的串行 简单易行，但由于数据在空间上的密度不均，容易 计算改为并行计算，即对数据集进行分组，将各组 在一个区域内大量集中，从而使得分组结果形成一 数据分配到不同的计算节点分别计算，从而减少总 些不易处理的狭长带，对分组后的数据处理带来很 [7] 多问题；（3）赵春宇等人提出Hilbert 曲线（Hilbert 计算任务的完成时间 。近年来，对空间数据分组