摘要
主流R树变体结点分裂目标优化策略仅能以单一的优化目标为主,造成其他优化目标过度忽略。针对这一问题,提出一种R树的形位多目标结点分裂算法。将结点分裂视为多目标优化问题,利用Pareto优化方法求解,其中将候选分裂解的周长之和与重叠度视为多目标优化问题的目标。根据上溢结点子结点位置与形状的多目标优化结果选取分裂轴,从而有效减少候选分裂解个数,提高分裂效率。实验结果证明,与CR树、RR*树算法相比,R树的形位多目标聚类结点分裂算法在R树结点分布与数据分布一致性、构建效率及空间查询等方面均有所改善。
The mainstream methods of node splitting of R-tree are mainly based on single objective optimization,which lead to excessive ignorant of others objective optimization. For this problem,an algorithm of form and position,multiple goals,clustering was proposed. The process of choosing optimum solution in the algorithm of choosing subtree and splitting node can be considered as the multi-objective optimization.The decision vector includes perimeter,overlap and increment of both for node bounding box after inserting object. The split axis can be chose with the distribution of form and position of children node in the overflownode along each axial direction,which can improve the consistency between the distribution of the R-tree index node and the distribution of data points. The experimental results showthat,the R-tree built with the algorithm of form and position,multiple goals,clustering is better than CR-tree and RR＊-tree in synthetic performance in aspects as the distribution of node,the efficiency of building R-tree and spatial query.
出处
《组合机床与自动化加工技术》
北大核心
2017年第12期51-53,58,共4页
Modular Machine Tool & Automatic Manufacturing Technique
基金
国家自然科学基金(51575326)
山东省自然科学基金(ZR2015EM031)
关键词
R树
多目标优化
形位分布
聚类
R-tree
multi-objective optimization
the distribution of form and position
clustering
