基于CURE聚类算法的静态R树构建方法

计算机科学 ›› 2015, Vol. 42 ›› Issue (10): 193-197.

基于CURE聚类算法的静态R树构建方法

李松,崔环宇,张丽平,经海东

哈尔滨理工大学计算机科学与技术学院哈尔滨150080,哈尔滨理工大学计算机科学与技术学院哈尔滨150080,哈尔滨理工大学计算机科学与技术学院哈尔滨150080,哈尔滨理工大学计算机科学与技术学院哈尔滨150080

出版日期:2018-11-14 发布日期:2018-11-14
基金资助:
本文受黑龙江省教育厅科学研究项目(12541128)资助

Static R-tree Building Method Based on Cure Clustering Algorithm

LI Song, CUI Huan-yu, ZHANG Li-ping and JING Hai-dong

Online:2018-11-14 Published:2018-11-14

摘要/Abstract

摘要： R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。

关键词: 传统R树,静态R树,CURE算法,海量数据

Abstract: The R tree index structure plays a great role in spatial objects query and complex spatial relations query.The traditional spatial index structure of R tree is generated dynamically.The structure of its tree is realized according to the continuous insertion algorithm. It uses the way of splitting child node to generate the root node of R tree.Dynamic gene-ration algorithm will cause low minimum utilization rate of the node of R tree.In order to make up for the inadequacy of dynamically generated R tree,a static R tree algorithm based on CURE algorithm was proposed,and the CU_RHbuilt tree building method was put forward.This algorithm can not only effectively deal with massive data,recognize clusters of any shape,reduce the overlap degree of rectangles,but also greatly reduce the computational cost as partitioning technology is adopted.The spatial utilization is rather high.The R tree node splitting method based on CURE algorithm was further proposed.Theoretical research and experiment show that the query efficiency of the proposed method is rather high.

Key words: Traditional R-tree,Static R-tree,CURE algorithm,Massive data

李松,崔环宇,张丽平,经海东. 基于CURE聚类算法的静态R树构建方法[J]. 计算机科学, 2015, 42(10): 193-197. https://doi.org/

LI Song, CUI Huan-yu, ZHANG Li-ping and JING Hai-dong. Static R-tree Building Method Based on Cure Clustering Algorithm[J]. Computer Science, 2015, 42(10): 193-197. https://doi.org/

参考文献

[1] 李松,张丽平,孙冬璞.空间关系查询与分析[M].哈尔滨:哈尔滨工业大学出版社,2011
[2] 张明波,陆峰,申排伟.R树家族的演变与发展[J].计算机学报,2005,28(3):289-300 Zhang Ming-bo,Lu Feng,Shen Pai-wei.The Evolvement and Progress of R-Tree Family[J].Chinese Joural of Computers,2005,28(3):289-300
[3] Guttman A.R-Trees A Dynamic Index Structure for SpatialSearching[C]∥Proceedings of Annual Metting(SIGMOD’84).1984:18-21
[4] 李松,郝忠孝.球面上最近邻空间关系处理方法[J].计算机工程,2010,6(6):91-93 Li Song,Hao Zhong-xiao.Methods For Handing Nearest Neighbor Spatial Relation on Spherical Surface[J].Computer Engineering,2010,6(6):91-93
[5] 张栋良,唐俊.基于路由机制的时变路网k近邻算法[J].计算机科学,2013,0(2):30-34 Zhang Dong-liang,Tang Jun.k-Nearest Neighbor Algorithm in Dynamic Road Network Based on Routing Mechanism[J].Computer Science,2013,0(2):30-34
[6] 张丽平,李松,赵纪桥,等.受限区域内的单纯型连续近邻链查询方法[J].计算机应用,2014,34(2):406-410 Zhang Li-ping,Li Song,Zhao Ji-qiao,et al.Simple continuous near neighbor chain query in constrained regions[J].Journal of Computer Applications,2014,34(2):406-410
[7] Abdel R,Zaki M,Jizhe X,et al.Data-intensive Spatial Indexing on the Clouds[J].Procedia Computer Science,2013(18):2615-2618
[8] Brakatsoulas S,Pfoser D,Theod Y.Revisiting R-tree Construction Principles[C]∥Proceedings of the 6th East European Conferences on Advances in Databases and Information Systems.London:Springer Verlag,2002:149-162
[9] 黄继先,鲍光淑,夏斌.基于混合聚类算法的动态R-树[J].中南大学学报,2005,37(2):366-370 Huang Ji-xian,Bao Guang-shu,Xia Bin.A dynamic R-tree index based on hybrid clustering algorithm[J].J.Cent.South Univ,2005,37(2):366-370
[10] 刘润涛,郝忠孝.R-树和四叉树的空间索引结构:RQOP_树[J].哈尔滨工业大学学报,2010,42(2):323-327 Liu Run-tao,Hao Zhong-xiao.Spatial index structure based on R-tree and quadtree:RQQP_tree[J].Journal of Harbin Institute of Technology,2010,42(2):323-327
[11] 汪璟玢.一种结合空间聚类算法的R树优化算法[J].计算机工程与应用,2014,50(5):112-115 Wang Jing-bin.Optimization algorithm for R-tree combining with spatial-clusting[J].Computer Engineering and Application,2014,0(5):112-115
[12] 刘润涛,安晓华,高晓爽.一种基于 R-树的空间索引结构[J].计算机工程,2009,35(23):32-34 Liu Run-tao,An Xiao-hua,Gao Xiao-shuang.Spatial Index Struction Based on R-tree[J].Computer Engineering,2009,35(23):32-34
[13] Jesper J W.Constructing the R* Consensus Tree of Two Trees in Subcubic Time[J].Algorithmica,2013(66):329-345
[14] Nikhil D K.P＋ and R* Tree Indexing Techniques on DataWarehouses for Efficient Database Indexing[J].International Journal of Engineering Associates,2013,2(5):31-34
[15] 李松,张丽平,朱德龙,等.动态受限区域内的单纯型连续近邻链查询方法[J].计算机科学,2014,1(6):136-141 Li Song,Zhang Li-ping,Zhu De-long,et al.Simple Continues Near Neighbor Chain Query in Dynamic Constrained Regions[J].Computer Science,2014,1(6):136-141

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed