OALib Journal期刊
基于N-KD树的空间点数据分组算法
DOI: 10.3724/SP.J.1047.2015.00001
Keywords: 点数据 ,K-D树 ,离散性 ,N-KD树 ,动态分组 ,数据并行
Abstract:
随着科学技术的进步,地理空间数据的分析处理面临着数据量膨胀和计算量高速增长的双重挑战,为了解决海量数据处理速度慢的问题,本文针对空间分布不均匀的点数据,从数据并行的角度,以保持数据的空间邻近性及保证数据分组后各组数据量负载均衡为目标,提出基于N-KD树(Number-KDimensionTree)数据动态分组的方法,其是一种面向实时变化(数据量和数据空间范围变化)的空间数据动态分组方法。该方法借鉴K-D树的创建和最临近点搜索的思想,通过方差判断数据分布稀疏程度,利用最临近点搜索方法处理边界点,实现空间范围的不均等切分,保证数据分组后各组数据量基本均衡。试验表明,该方法具有较好的动态分组效果与较高的计算效率;支持各种分布状态的空间点数据的分组;分组后各组数据量负载均衡;分组算法本身有支持并行、支持分布式协同工作模式的特点。
References
[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] 王碧,霍红卫.基于K-D树的多维数据分布方法[J].计算机工程,2003,29(3):105-107. [15] Abudalfal S, Mikki M. A dynamic linkage clustering using KD-tree[J]. The International Arab Journal of Information Technology, 2013,10(3):283-289. [16] 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 [17] 王永杰,孟令奎,赵春宇.基于Hilbert 空间排列码的海量空间数据划分算法研究[J].武汉大学学报·信息科学版, 2007,32(7):650-653. [18] 周艳,朱庆,张叶延.基于Hilbert 曲线层次分解的空间数据划分方法[J].地理与地理信息科学,2007,23(4):13-17.
Full-Text
Contact Us
service@oalib.com
QQ:3279437679
WhatsApp +8615387084133
