摘要： 根据R*树节点硬盘主引导记录(MBR)特征，在不改变最小外包矩形特征的前提下，通过区域扫描对正交MBR重叠区域边界建立二叉线段树，以此为基础分别计算面积和周长，有效改善了R*树节点结构。理论分析和实验均表明，与未经过重叠区域计算的R*树相比，经计算的R*树节点比较次数平均下降了近60%，准确率提高了约60%。

关键词: 近似查询, 硬盘主引导记录, 重叠区域, R*树

Abstract: According to the characteristics of Master Boot Record(MBR) in R*-tree, this paper creates the binary segment tree by sweeping the orthogonal overlapping region. Sweeping algorithm calculates the area and perimeter of the orthogonal overlapping region without changing the characteristics of the minimum bounding rectangle. Comparison of the evaluation reveals that the number of node access of R*-tree decreases by nearly 60 percent and the search accuracy increases by about 60 percent after calculating the overlapping compared with the algorithm uncalculated. Analysis and experimental results show that the algorithm can improve the accuracy and efficiency of route selection with inserting large amount of the spatial objects in approximate search by calculating the overlapping in advance.

Key words: approximate search, Master Boot Record(MBR), overlapping region, R*-tree

中图分类号: 

• TP311.13