近似查询中重叠区域的扫描计算  

Sweeping Calculation of Overlapping Region in Approximate Search

作　　者：李博涵[1] 郝忠孝[1] 

机构地区：[1]哈尔滨理工大学计算机科学与技术学院,哈尔滨150080

出　　处：《计算机工程》2008年第13期10-12,共3页Computer Engineering

基　　金：黑龙江省自然科学基金资助项目(F200601)

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

关 键 词：近似查询 硬盘主引导记录 重叠区域 R^＊树 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]