计算机科学 ›› 2015, Vol. 42 ›› Issue (10): 193-197.
李松,崔环宇,张丽平,经海东
LI Song, CUI Huan-yu, ZHANG Li-ping and JING Hai-dong
摘要: R树索引结构在空间对象查询和复杂空间关系查询方面具有重要作用。传统空间索引结构R树是动态生成的,树的结构是根据连续插入算法实现的,通过分裂子节点直至生成R树的根节点。动态生成算法会导致R树节点最小外包矩形之间的大量重叠,影响空间查询效率,且空间利用率不高。为了弥补动态生成R树的不足,提出了基于CURE算法的静态R树生成方法,给出CU_RHbuilt建树算法,该算法不仅能有效地处理海量数据,识别任何形状的簇,减少矩形重叠度,而且采用划分技术可较大程度地减小计算代价,空间利用率较高。进一步提出了基于CURE算法的R树节点分裂方法。理论研究与实验表明,所提方法具有较高的查询效率。
[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! |
|