计算机工程 ›› 2010, Vol. 36 ›› Issue (12): 80-82.doi: 10.3969/j.issn.1000-3428.2010.12.028

• 软件技术与数据库 • 上一篇    下一篇

基于QCR-树的空间索引方法

高 云1,侯贵宾2,张 辉1,刘永山1,石伟铂3   

  1. (1. 燕山大学信息科学与工程学院,秦皇岛 066004;2. 秦皇岛港股份有限公司技术中心,秦皇岛 066004;3. 燕山大学图书馆,秦皇岛 066004)
  • 出版日期:2010-06-20 发布日期:2010-06-20
  • 作者简介:高 云(1983-),女,硕士研究生,主研方向:空间数据库;侯贵宾,高级工程师、硕士;张 辉,硕士研究生;刘永山,教授、博士、博士生导师;石伟铂,硕士
  • 基金项目:
    河北省自然科学基金资助项目(F2009000473)

Spatial Index Method Based on QCR-tree

GAO Yun1, HOU Gui-bin2, ZHANG Hui1, LIU Yong-shan1, SHI Wei-bo3   

  1. (1. College of Information Science and Engineering, Yanshan University, Qinhuangdao 066004;2. Technology Center, Qinhuangdao Port Co., Ltd., Qinhuangdao 066004; 3. Library of Yanshan University, Qinhuangdao 066004)
  • Online:2010-06-20 Published:2010-06-20

摘要: 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

中图分类号: