摘要: QR-树处理海量空间数据时,其深度和R-树内目录矩形的重叠面积会变大,导致查询效率降低。针对该问题采用K-means算法对索引对象进行聚类分析,构造新的聚类中心使其能处理具有多种形体的索引对象,并在QR-树中引入超结点存储聚类结果。提出一种QCR-树空间索引结构来提高查询效率,给出QCR-树的插入、删除和查询算法。实验结果表明QCR-树的查询性能优于QR-树,适用于海量数据。
关键词:
空间索引,
QR-树,
QCR-树,
K-means算法,
超结点
Abstract: The depth of QR-tree and the overlapping areas of directory rectangles of R-tree will increase when the massive spatial data is processed by the QR-tree, which incures lower query efficiency. Aiming at this problem, this paper carries out clustering analysis of index objects by K-means algorithm, and a novel formula of clustering center is constructed to make K-means deal with index objects with various forms. It introduces super nodes for storing the clustering results and proposes a QCR-tree spatial index structure to improve the query efficiency. The insertion, deletion and query algorithms of QCR-tree are presented. Experimental results show that QCR-tree, whose query performance is higher than QR-tree, is fit for processing the massive data.
Key words:
spatial index,
QR-tree,
QCR-tree,
K-means algorithm,
super node
中图分类号:
高云, 侯贵宾, 张辉, 刘永山, 石伟铂. 基于QCR-树的空间索引方法[J]. 计算机工程, 2010, 36(12): 80-82.
GAO Yun, HOU Gui-Bin, ZHANG Hui, LIU Yong-Shan, DAN Wei-Bo. Spatial Index Method Based on QCR-tree[J]. Computer Engineering, 2010, 36(12): 80-82.