摘 要：对R- 树空间索引查询效率低下的问题，提出一种改进的PSR- 树索引方法。PSR- 树使用贪心算法找到要分裂的节点中对应的MBR 的最小边界值，在最小边界值和非最小边界值中分别随机选择一个边界对象，用选择得到的这两个对象为分裂后两个新增节点首选空间数据对象进行分裂操作，建立好PSR- 树后并写入节点。实验表明，PSR- 树可以有效地减少节点中最小外接矩形的重叠面积，时间响应上比已有的R- 树索引快，PSR- 树从上述两个方面提高了查询效率。
关键词：R- 树；最小外接矩形；节点分裂；最小边界值
中图分类号：TP391；TP301.6 文献标识码：A 文章编号：2096-4706（2020）22-0086-06
An Improved R-tree Node Splitting Optimization Algorithm
HE Jianying
（School of Intelligent Manufacturing，Sichuan University of Arts and Science，Dazhou 635000，China）
Abstract：To solve the problem of low efficiency of R-tree space index query，an improved PSR-tree index method is proposed.The PSR-tree uses a greedy algorithm to find the minimum boundary value of the corresponding MBR in the node to be split. A boundary object is randomly selected from the minimum boundary value and the non-minimum boundary value，use the selected two objects to perform the split operation for the two newly-added node preferred spatial data objects after splitting，and then write the node after the PSR-tree is established. The experiment shows that PSR-tree can effectively reduce the overlap area of the MBR in the node，and the time response is faster than the existing R-tree index，PSR-tree improves the query efficiency from these two aspects.
Keywords：R-tree；MBR；node splitting；minimum boundary value
基金项目：四川革命老区发展研究中心重点项目（SLQ2020SA-01）；四川文理学院重点项目（2018KZ001Z）；四川文理学院教改项目（2020JZ001）
参考文献：
[1] 陈菲，秦小麟. 空间索引的研究 [J]. 计算机科学，2001，28（12）：59-62.
[2] 张明波，陆锋，申排伟，等.R 树家族的演变和发展 [J].计算机学报，2005，28（3）：289-300.
[3] BRAKASTSOULAS S，PFOSER D，TTHEODORIDIS Y.Revisiting R-tree construction principles [C]//Proceedings of the 6thEast European Conference on Advances in Databases and InformationSystems.Springer-Verlag，2002：149-162.
[4] 孙殿柱，李心成，田中朝，等. 基于动态空间索引结构的三角网格模型布尔运算 [J]. 计算机辅助设计与图形学学报，2009，21（9）：1232-1237.
[5] 徐明. 基于节点分裂优化的R- 树索引结构 [J]. 计算机应用研究，2016，33（12）：3530-3534.
[6] GUTTMAN A. R-Trees：A Dynamic Index Structure forSpatial Searching [J].Acm Sigmod Record，1984，14（2）：47-57.
[7] DU Q，GUNZBURGER M，JU L L，et al. Centroidal VoronoiTessellation Algorithms for Image Compression，Segmentation，and Multichannel Restoration [J].Journal of Mathematical Imaging andVision，2006，9（10）：177-194.
[8] PROIETTI G，FALOUTSOS C. Analysis of range queries andself-spatial join queries on real region datasets stored using an R-tree [J].IEEE Transactions on Knowledge and Data Engineering，2000，12（5）：751-762.
[9] 胡昱璞. 动态k 值聚类的R- 树空间索引构建 [D]. 太原：太原理工大学，2016.
[10] 陈敏，王晶海.R*- 树空间索引的优化研究 [J]. 计算机应用，2007（10）：2581-2583.
[11] DRAISBACH U，NAUMANN F，SZOTT S，et al. Adaptivewindows for duplicate detection [C]//Proceedings of the 2012 IEEE 28thInternational Conference on Data Engineering.IEEE，2012：1073-1083.
作者简介：贺建英（1979—），女，汉族，四川金堂人，教师，副教授，硕士，主要研究方向：软件工程、机器学习。