Computer Science ›› 2015, Vol. 42 ›› Issue (10): 193-197.

Previous Articles     Next Articles

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: 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

[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

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!