基于最小生成树的R<sup>*</sup>-树结点分裂算法

孙殿柱; 孙永伟; 康新才; 史阳

您当前的位置：

首页 >

文章列表页 >

基于最小生成树的R^*-树结点分裂算法

更新时间：2025-05-08

- 基于最小生成树的R^*-树结点分裂算法
- Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree
- 西安交通大学学报 2011年45卷第5期页码：127-130
- 作者机构：
  
  山东理工大学机械工程学院,山东,淄博,255049
- 作者简介：
- 基金信息：
  
  : 2010-07-20. 作者简介: 孙殿柱(1956-),男,教授. 基金项目: 国家自然科学基金资助项目(51075247)
- DOI：
  中图分类号： TP391.72
- 网络首发：2011-05-10，
  
  纸质出版：2011
- 稿件说明：
移动端阅览
孙殿柱, 孙永伟, 康新才, 等. 基于最小生成树的R^*-树结点分裂算法[J]. 西安交通大学学报, 2011,45(5):127-130.

Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree[J]. 2011, 45(5): 127-130.
孙殿柱, 孙永伟, 康新才, 等. 基于最小生成树的R^*-树结点分裂算法[J]. 西安交通大学学报, 2011,45(5):127-130. DOI：

Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree[J]. 2011, 45(5): 127-130. DOI：

摘要

针对R

树应用到逆向工程领域时遇到的适用性差等问题

提出了一种新的R

树结点分裂算法.该算法将R

树索引结点表示为轴向包围盒

依据轴向包围盒外接球间的重叠度计算结点相似度

并将其作为权值构建结点无向连通图

用来求解结点无向连通图的最小生成树.沿最大权值边将最小生成树分裂为2棵子树

并基于结点外接球体积对R

树结构进行优化

从而实现了R

树结点分裂.实例表明

树结点分裂算法可处理各种复杂数据的结点分裂问题

能够有效地提高R

树的构建效率及空间数据的查询效率.

Abstract

Aiming at the problems of R

tree for reverse engineering of weak application

a new node splitting algorithm of R

tree is proposed. The nodes of R

tree are all expressed as their minimum bounding boxes. Then

the node comparability value is weighed with circum-sphere of the minimum bounding boxes. The minimum spanning tree is constructed based on the connected undirected graph of node comparability value

and the minimum spanning tree is divided into two sub-trees on the edge of the maximum weight

which gets effective for optimizing the structure of R

tree and improving the efficiency of node splitting.

关键词

Keywords

references

卫炜,张丽艳,周来水.一种快速搜索海量数据集k-近邻空间球算法 [J].航空学报,2006,27(5):944-948.

WEI Wei,ZHANG Liyan,ZHOU Laishui.A spatial sphere algorithm for searching k-nearest neighbors of massive scattered points [J].Acta Aeronautica Astronautica Sinica,2006,27(5):944-948.

史桂蓉.反向工程几何建模关键技术 [D].上海:上海交通大学,2000.

孙肖霞,孙殿柱,李延瑞,等.散乱数据点的快速三角剖分算法 [J].中国机械工程,2006,17(S2):245-248.

SUN Xiaoxia,SUN Dianzhu,LI Yanrui,et al.A fast mesh generation algorithm for unorganized points [J].China Mechanical Engineering,2006,17(S2):245-248.

BECKMASN N,KRIEGEL H P,SCHNEIDER R,et al.The R/sup*-tree: an efficient and robust access method for points and rectangles[C]∥Proceedings of SIGMOD. New York,USA: ACM, 1990:322-331.

ZHU Qing,GONG Jun,ZHANG Yeting.An efficient 3D R/sup*-tree spatial index method for virtual geographic environments [J].ISPRS Journal of Photogrammetry and Remote Sensing,2007,62(3):217-224.

张明波,陆锋,申排伟,等.R树家族的演变和发展 [J].计算机学报,2005,28(3):289-300.

ZHANG Mingbo,LU Feng,SHEN Paiwei,et al.The evolvement and progress of R-tree family [J].Chinese Journal of Computers,2005,28(3):289-300.

黄继先,鲍光淑,夏斌.基于混合聚类算法的动态R-树[J].中南大学学报:自然科学版,2006,37(2):366-370.

HUANG Jixian,BAO Guangshu,XIA Bin.A dynamic R-tree index based on hybrid clustering algorithm [J].Journal of Central South University:Science and Technology,2006,37(2):366-370.

孙殿柱,范志先,李延瑞,等.散乱数据点云型面特征分析算法的研究与应用 [J].机械工程学报,2007,43(6):133-136.

SUN Dianzhu,FAN Zhixian,LI Yanrui,et al.Research and application of surface feature analysis scatter data points [J].Chinese Journal of Mechanical Engineering,2007,43(6):133-136.

孙殿柱,田中朝,李延瑞,等.基于四维聚类的R/sup*-树结点分裂算法[J].机械工程学报,2009,45(10):180-184.

SUN Dianzhu,TIAN Zhongchao,LI Yanrui,et al.Node splitting algorithm of R/sup*-tree based on four-dimensional [J].Chinese Journal of Mechanical Engineering,2009,45(10):180-184.

孙殿柱,李延瑞,朱昌志,等.各类几何对象统一表示的R/sup*-tree结点分裂算法 [J].华中科技大学学报:自然科学版,2010,38(2):55-58.

SUN Dianzhu, LI Yanrui, ZHU Changzhi,et al.Node splitting algorithm for R/sup*-tree based on united expression of all geometry objects [J].Journal of Huazhong University of Science and Technology:Nature Science Edition,2010,38(2):55-58.

RAJASEKARAN S. On the Euclidean minimum spanning tree problem, Technical Report BECAT/CSE [R]. Storrs, CT, USA: Univ. of Connecticut,2004.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

逆向工程中一种鲁棒的平移对称提取算法

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

张角凹坑气膜孔对双层壁气膜冷却特性的影响

扇贝仿生密封腔室内超临界二氧化碳泄漏流湍动能耗散机理研究

冷库水平空气幕热湿阻隔性能数值模拟研究

基于最小生成树的R*-树结点分裂算法

Node Splitting Algorithm of R*-Tree Based on Minimum Spanning Tree

DOI：

摘要

Abstract

关键词

Keywords

references

基于最小生成树的R^*-树结点分裂算法

Node Splitting Algorithm of R^*-Tree Based on Minimum Spanning Tree