EN中文

Journal of Geo-information Science >

2015 , Vol. 17 >Issue 1: 1 - 7

DOI: https://doi.org/10.3724/SP.J.1047.2015.00001

Orginal Article

A Spatial Point Data Grouping Algorithm Based on the N-KD Tree

  • WEI Haitao , 1, 2 ,
  • DU Yunyan , 2, * ,
  • REN Haowei 1, 2 ,
  • LIU Zhang 2 ,
  • YI Jiawei 2 ,
  • XU Kaihui 1, 2
Expand
  • 1. Shandong University of Science and Technology, Qingdao 266510, China
  • 2. LREIS, Institute of Geographic Sciences and Natural Resources Research, CAS, Beijing 100101, China
*Corresponding author: DU Yunyan, E-mail:

Received date: 2014-02-14

  Request revised date: 2014-07-19

  Online published: 2015-01-05

Copyright

《地球信息科学学报》编辑部 所有
Fold

Abstract

The large amount of calculations with a continuously high-speed growth required in current development of computational technology presents a great challenge to the research of spatial data processing in geography. To accelerate the processing speed of constantly updated real-time data that distributed unevenly, this study developed a dynamic grouping method based on the Number-K Dimension (N-KD) Tree technique. The method employs a data parallel algorithm to preserve spatial proximity and balance the data loads after grouping the real-time data that vary both in quantity and spatial domain. Based on the KD Tree creation, the algorithm measures the data sparsity according to the mathematic variance, addresses the point data near boundaries according to the nearest searching approach, and achieve an unequal data partition with respect to space while having balanced data loads. Experiments reveal that the method is capable of efficiently grouping the point data that have various spatial distributions and balancing the data amount among these groups. The algorithm also supports parallel computing and distributed collaborative working model, which highlights the practical values in its applications.

Key words： point data; discreteness; N-KD Tree; K-D Tree; dynamic grouping; data parallel

Cite this article

WEI Haitao , DU Yunyan , REN Haowei , LIU Zhang , YI Jiawei , XU Kaihui . A Spatial Point Data Grouping Algorithm Based on the N-KD Tree[J]. Journal of Geo-information Science, 2015 , 17(1) : 1 -7 . DOI: 10.3724/SP.J.1047.2015.00001

1 引言

空间点数据集是GIS（Geographic Information System）空间分析中常见的数据对象之一,例如,利用空间点集构建DEM,空间点数据的等值线生成,利用空间点集构建三角网等数据分析与数据处理均涉及到空间点数据集[1-6]。然而,随着空间点数据量的增大,串行计算对空间点数据的处理效率很难满足实际应用的要求。为了提高大数据量空间数据计算效率,目前常用的方法是将空间点集的串行计算改为并行计算,即对数据集进行分组,将各组数据分配到不同的计算节点分别计算,从而减少总计算任务的完成时间[7]。近年来,对空间数据分组方法的研究已成为网络GIS中重点关注的研究问题之一[8-11]。
空间数据分组与传统数据分组最大区别在于分组时要考虑到数据的空间属性,只有如此的数据分组方法才能减少计算机空间计算时的额外开销,从而减少其空间计算所需的时间,最大限度地提高计算效率[11]。目前,空间分组的方法主要有：（1）网格分割法,即对数据按照地理空间范围（经纬度坐标）进行等分,实现对空间点数据的分组,该方法可保持空间数据集的空间邻近性,简单易实现,但由于数据分布不均匀,上述方法会造成各组数据的数据量失衡,导致整体时间效率低下;（2）Lee等人提出单向划分法[12],即仅仅按照空间数据的某个坐标轴统计数据量,对数据进行等量分组,该方法同样简单易行,但由于数据在空间上的密度不均,容易在一个区域内大量集中,从而使得分组结果形成一些不易处理的狭长带,对分组后的数据处理带来很多问题;（3）赵春宇等人提出Hilbert曲线（Hilbert space-filling curve）的层次分解划分方法[13-15],即通过空间数据集上生成Hilbert曲线,将二维的空间数据进行Hilbert排序,排序后的数据按数据量要求分组,该方法存在时间消耗量大,分组效率低的缺点;（4）Abudalfa等利用K-D树的思想提出DLCKDT（a Dynamic Linkage Clustering using KD-Tree）分组方法[17],即将空间数据进行分组抽稀后用于空间聚类的加速运算,但是,方法进行分组耗时长,且分组的数量由于K-D树建树特点决定其分组数只能是2的n次方,不能实现对数据的任意分组。
实际应用中,系统与用户的交互决定了处理的数据具有数据量动态可变且所在区域不确定的特点,要求数据分组算法可以面向任务、实时动态的完成数据分组。由于上述几种方法各自存在数据均衡性差、运行效率低、不能实现任意分组等缺点,在不需数据预处理的情况下很难满足实际需求,因此,本文提出一种基于N-KD树的空间点数据分组算法,其可根据用户提交的任务点,实时地完成任意分组个数的数据分组。

2 基于K-D树改进的空间数据分组算法

2.1 K-D树空间分组的原理与方法

K-D树是在K维欧几里德空间组织点的数据结构,一般用于多维键值搜索,在建立空间数据索引时,每个节点都为K维点的一种特殊的二叉树,所有非叶子节点可视作一个超平面（n维欧氏空间中维度等于一的线性子空间）,把空间分割成两部分[18],超平面左边的点代表节点的左子树,超平面右边的点代表节点的右子树。超平面的方向可用下述方法来选择：对所有数据集,统计它们在每个维度上的数据方差,挑选出最大值对应的维度,点数据按其维度方向的值排序,选出位于正中间的点数据,沿该点数据,在该维度方向上进行数据分割,如果按照x轴划分,所有x值小于指定值的节点都会出现在左子树,所有x值大于指定值的节点都会出现在右子树。

2.2 基于K-D树的改进的空间分组算法（N-KD树算法）

本文提出了基于K-D树改进的空间分组算法即K维空间点数据等数据量分组算法（简称为N-KD树空间分组算法）,其借鉴K-D树建树方法,并分别对数据分组思想以及数据划分方法作了相应的改进,对空间实行不对等划分,数据划分的终止条件是当叶子结点的个数与分组个数相等,与传统的先建索引后分组的方法相比,大大地提高了分组效率。由于K-D树是一种特殊的二叉树,故本算法采用二叉树的结构对数据进行切分和存储,点数据看做是一个集合,其具体原理为：
A = { P i = ( x i , y i ) | i = 1,2 , 3 , .... , n } （1）
式（1）中,Pi为集合A中的点;i为A中点的个数。本算法的最终目标是将点数据,按照其空间特性进行划分,使得 A = A 1 ⋃ A 2 ⋃ … ⋃ A n ,且每个集合内点数据量基本达到数据均衡。其中,数据切分的方法是对点空间集在X、Y维度上做方差计算,根据计算结果判断点数据集在X,Y维度上的离散程度,并确定整个数据集的划分方向。若SX>SY（SX、SY分别表示X、Y纬度上的方差）,则在X方向划分,反之在Y方向划分。通过选择方差大的维度作为划分数据集的维度的方法可确保所划分的维度上点集分布的比较稀疏,这样可得到较高分辨率的分组结果。
在数据切分过程中,若对待分组数据进行等分会造成分组个数恒等于2n,难以满足实际的要求,故该算法并不是采用简单的等分数据方法。为满足数据的任意分组和分组后数据量均衡的要求,并确保最终构建的二叉树为平衡二叉树,对数据分组的方法作了相应调整,具体的划分方法如图1所示。
Fig. 1 Flow chart of spatial data partition

图1 空间数据分割算法流程图

R为数据分组时右子树中包含的分组组数,初始值为0;L为数据分组时左子树中包含的分组组数,初始值为0;k设计的分组个数;k为实际操作中的分组参数,其值在分组开始时等于k;n为待定参数;a[i]为第i次分组左右子树比。
我们采用数学方法证明了本算法所构建的二叉树为平衡二叉树,具体过程如下：
当分组数为1时不分组,故不参加讨论,当分组数为非1时k的取值可表示为以上的形式,随着n取值的不同,A到C的线段可表示取遍任意非1,0的自然数。
（1）显然,当 K = 2 n , 2 n + 1 时,算法采取等分方式,故所得的二叉树为 n 层满二叉树;
（2）当 0 < K - 2 n < 2 n - 1 时,
R = 2 n - 1 右子树满足等分条件,故所得二叉树为 n - 1 层满二叉树;
L = K - 2 n - 1 > 2 n - 1 以文中划分方法得二叉树为 n 层平衡二叉树;
故所得二叉树为 n 层平衡二叉树。
（3）当 2 n - 1 ≤ K - 2 n < 2 n 时,
L = 2 n 左子树满足等分条件,故所得二叉树为n层满二叉树;
R = K - 2 n > 2 n - 1 ,当 K 取B点时所得右子树为 n - 1 层平衡二叉树;
当 2 n + 2 n - 1 < K < 2 n + 1 时,以文中划分方法得二叉树为n层平衡二叉树;
故所得二叉树为n层平衡二叉树。
综上所述,本算法所构建的二叉树为平衡二叉树。与传统K-D树分组算法只能将空间数据集分为2n组相比较,N-KD树空间分组算法可满足实际应用中以任意个数分组的要求。
N-KD树空间分组算法切分数据时,在切分方法上也进行了相应的调整,具体为：在判断完切分方向（X方向或是Y方向）后,通过设计分组个数K确定分组参数k和n,使得k=K,n满足条件 2 n < k < 2 n + 1 。在分别判断k是否等于 2 n + 1 以及 k - 2 n 与 2 n - 2 n - 1 的大小关系后,确认左右子树应分给多少组数据,而后各自乘以各组包含的数据量,得到左右子树分得的数据量。在这种方法的划分下,左右子树中会有一个子树包含的分组个数为2n,另一个情况不定。对于包含2n的部分在以后的过程中等分,另外一组则重复上述操作过程,直至分组 结束。

3 空间点数据分组算法案例分析

3.1 实验数据

为了验证本文方法,作者进行多次试验。实验采用中国南海海域（100°E~124°E,0°N~25°N）1991-2005年全球表层漂流浮标数据和全球剖面浮标数据,共有212 280个点,其空间分布如图2所示。
Fig. 2 Multi-source ocean buoy data visualization of the South China Sea

图2 中国南海多源海洋浮标数据可视化图

实验中,数据量分别为20万个（212 280）、10万个（118 417）、5万个（53 074）时,采用本文方法进行空间分割实验,分组个数为4、5、6、7、8、9、10,记录其分组时间。为了简化图形输出,以4、6、8组为例,给出空间数据的分组效果图（表1）。
Tab. 1 Test sample plots

表 1 测试实例图组表

3.2 实验结果

（1）分组的结果
由上述不同数据量的空间分组效果（表1）可得,随着数据量和空间范围的改变,其分区可以灵活地调整,且分组后各组数据在空间分布上呈现规则的矩形,保持了数据的空间邻近性,易于对各组数据进行空间分析。以上实验结果显示,本算法具有实时动态分组的能力,可满足用户交互时,针对自己感兴趣的区域,提交不同的计算任务所包含的不同区域的数据,进行实时动态分组。传统的静态分组预处理后,针对整个区域的数据进行一次建树,针对整个区域的部分数据分组,这部分数据的索引会被破坏,不能实现数据分组,鉴此,本算法具有很好的实用性。
（2）不同数据量不同分组的用时及数据均衡分析
由表2和图3可知,N-KD树空间分组算法随着处理的数据量和分组数的增加,分组时间会有所增加,但增加的趋势并不是很明显,也没有出现陡增的情况。就一定数据量分组耗时而言,N-KD树空间分组算法具有较好的时间效率。
Tab. 2 Time consuming and number of data points in each group regarding to different data quantity and different partition number

表 2 不同数据量、不同分组的用时及数据均衡情况

点集数据量（个） 不同数据量在各分组情况下的耗时（s）及数据量（个）
4 5 6 7 8 9 10
212 280 27.97
(53 074)		 28.07
(42 447)		 28.49
(35 389)		 29.84
(30 319)		 30.29
(26 530)		 31.01
(23 586)		 31.54
(21 229)
118 417 14.58
(29 595)		 17.84
(23 677)		 20.57
(19 728)		 21.06
(16 908)		 21.06
(14 795)		 21.72
(13 136)		 23.04
(11 839)
53 074 5.94
(13 257)		 6.94
(10 607)		 7.74
(8 841)		 8.42
(7 570)		 8.88
(6 625)		 9.42
(5 891)		 9.54
(5 298)
Fig. 3 Time consuming in different data quantity and different partition number

图3 不同数据量、不同分组的用时折线图

（3）对分组结果的评价
由上述试验可得,N-KD树空间分组算法在保持数据空间邻近性的前提下,确保了分组算法的区域适应性和各组数据量均衡的特点。这样使得分组之后的数据并不用过多地考虑后期多个计算节点由于数据密度的不同,所带来的计算时间不同的影响,提高了空间计算的效率,且分组后的区域皆为规则的矩形,并没有出现很难处理的狭长条带。这便于后续的空间计算,在分组的时间上较有优势,且速度较快。

3.3 算法的分组实验对比分析

为了验证上述算法的分组效果,分组后各组的数据均衡情况,以及分组时间效率,本文用空间位置划分方法和传统的K-D树分组方法（Abudalfa[17]的分组方法）作了对比实验。首先,对整个数据集建立K-D树索引,然后,以K-D树的倒数第三层子节点为分组标志,按照K-D树建树原则将空间数据进行分组,以及N-KD树空间分组方法对数据量为212 280个点的南海多源浮标数据进行空间分组,分组结果如图4所示（以分为6组为例）。
Fig. 4 Test sample comparison

图4 测试对比图

在试验过程中,针对传统K-D树分组方法的分组数的限制做了相应改进,保留其建立完整K-D树空间索引后对数据进行分组的思想,在其建树后不是单一的以某一层节点为分组标志分组,而是在遇到要分非2的n次方（如5、6、7）组时,查找空间邻近的点,以数据量为依据分组。
由分组结果可知,上述方法都是将空间点数据集所处的空间范围分组成了若干个,保有数据的空间邻近性,但空间位置分组的方法由于数据分布的随机性,数据量出现了严重的失衡,而后2种方法在数据密集区对数据进行了切分,使切分后的各组数据量基本相等,为分布式计算架构下采用数据分组做并行计算提供方法。
表3给出了上述3种方法在不同分组数下,每个分组对应的数据量情况（以数据量为20万,分组个数为4和6为例）。
Tab. 3 The number of data in each group

表3 3种方法在不同的分组数下各个分组对应的数据量

组号 分为4组 分为6组
空间位置均分法 传统K-D树分组方法 N-KD树空间分组方法 空间位置均分法 传统K-D树分组方法 N-KD树空间分组方法
1 30 058 53 070 53 069 25 028 35 380 35 382
2 21 370 53 071 53 067 114 207 35 379 35 376
3 36 046 53 070 53 074 21 976 35 382 35 374
4 124 805 53 073 53 074 17 052 35 380 35 388
5 19 103 35 383 35 373
6 14 914 35 383 35 393
图5（a）为上述3种方法不同分组时,各组实际数据量与均分后数据量的最大差值。图5（b）为上述3种方法,不同分组时,实际数据量最大差值与均分后数据量的比率。
Fig. 5 The comparison figure of data load balance

图5 数据负载均衡对比图

从表2和图5（a）中可看出,N-KD树空间分组方法分组后的各个组的数据量继承了传统K-D树分组方法的优点,各组数据量相差只有10个点左右,但是,空间位置均分方法分组后的各个组的数据量相差很大,最大的差值在5000到7000个点。由图6可知,空间位置划分方法分组的差值是均分分组结果的2倍左右,而N-KD树空间分组方法则可忽略不计。分组后各个组数据量相差会影响后续的负载均衡问题,会增加整个空间数据计算任务的耗时,而N-KD树空间分组算法能保证将任意数据量的空间点集数据均分成等数据的若干组,解决了负载均衡,从而提高了整个空间点数据计算任务的效率。
Fig. 6 Time consuming comparisons among the three algorithms

图6 3种方法的耗时对比图

图6为相同数据量下空间位置划分法,传统K-D树分组法与N-KD树空间分组的耗时对比图。由图6可知,空间位置均分法与N-KD树空间分组两种方法的耗时基本相同（0.85左右）,而与传统K-D树分组法相比,N-KD树空间分组法耗时就少了很多（加速比为30左右）,因此,与空间位置直接划分方和传统K-D树分组方法相比,N-KD方法不但能保证数据量的负载均衡的分组算法本身也是一个效率较高的动态数据分组算法。

4 结论与展望

面对大数据时代来临的现实,以及实际应用的需求,本文针对数据量庞大的海洋空间点数据的特点,在分析总结已有的数据分组算法的基础上,结合应用端用户交互会使计算数据变更频繁的特点,提出了一种基于K-D树改进的分组算法（N-KD树空间分组方法）。实验证明,该算法分组耗时少（20万量级的数据,此方法较先建立索引后分组的算法节省近30倍的时间）;对于数据量庞大的空间点数据集,N-KD树空间分组方法可按照实际需求将其动态的切分成需要的若干组,保证各组数据间的负载均衡,使得实际应用中避免了多个计算节点由于数据密度不同带来的计算时间不同的影响;该算法具有区域适应性、保持分组数据的空间邻近性的特点。N-KD算法能较高效对不同空间范围、不同数据量、实时变更的空间点数据集动态完成空间分组。本文仍然存在着不足之处：算法考虑了数据的空间邻近性,但没有考虑数据的时间属性,在面对带有时间属性的过程数据时,不能确保将一个过程的数据分在一个组中。为了克服以上不足之处,今后的研究将加入增大数据分割粒度的方法,面向应用,完成地理信息数据的分组。

The authors have declared that no competing interests exist.

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
王劲峰,李连发,葛咏,等.地理信息空间分析的理论体系探讨[J].地理学报,2000,55(1):92-103.

[2]
杨海军,邵全琴.GIS空间分析技术在地理数据处理中的应用研究[J].地球信息科学,2007,9(5):70-75.

[3]
彭剑南. GIS空间分析方法研究[D].长春:吉林大学,2008.

[4]
Haining R.Spatial Data Analysis in the Social and Environment Science[M]. London: Cambridge University Press, 1994.

[5]
应龙根,宁越敏. 空间数据:性质、影响和分析方法[J].地球科学进展,2005,20(1):49-56.

[6]
史文中. 空间数据误差处理的理论与方法[M].北京:科学出版社,2000:15-38.

[7]
张发存,王馨梅,张毅坤.数字图像几何变换的数据并行方法研究[J].计算机工程,2005,31(22):159-161.

[8]
张书亮,吴宇,徐洁慧,等.网络GIS及其内容体系和应用分析[J].地球信息科学,2007,9(2):43-48.

[9]
胡圣武,朱燕霞.网络GIS 的发展及其应用[J].测绘工程,2007,16(4):5-9.

[10]
赵春宇. 高性能并行GIS中矢量空间数据存储与处理关键技术研究[D].武汉:武汉大学,2006.

[11]
田光. 并行计算环境中矢量空间数据的划分策略研究与实现[D].北京:中国地质大学,2011:2-4.

[12]
Lee D T, Schachter B J.Two algorithm for constructing a Delaunay Triangulation[J]. International Journal of Computer and Information Science, 1980,9(3):219-242.

[13]
赵春宇,孟令奎,林志勇.一种面向并行空间数据库的数据划分算法研究[J].武汉大学学报·信息科学版,2006,31(11):962-965.

[14]
王永杰,孟令奎,赵春宇.基于Hilbert空间排列码的海量空间数据划分算法研究[J].武汉大学学报·信息科学版,2007,32(7):650-653.

[15]
周艳,朱庆,张叶延.基于Hilbert曲线层次分解的空间数据划分方法[J].地理与地理信息科学,2007,23(4):13-17.

[16]
王碧,霍红卫.基于K-D树的多维数据分布方法[J].计算机工程,2003,29(3):105-107.

[17]
Abudalfal S, Mikki M.A dynamic linkage clustering using KD-tree[J]. The International Arab Journal of Information Technology, 2013,10(3):283-289.

[18]
Shevtsov M, Soupikov A, Kapustin A.Highly parallel fast KD-tree construction for interactive ray tracing of dynamic scenes[J]. EuroGraphics, 2007,26(3):395-404

Options
Outlines

/

〈 〉