Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (2): 173-181.DOI: 10.3778/j.issn.1673-9418.1506089

Previous Articles     Next Articles

R-tree Spatial Index Construction Based on Dynamical K-value Clustering Algorithm

HU Yupu, NIU Baoning+   

  1. School of Computer Science and Technology, Taiyuan University of Technology, Taiyuan 030024, China
  • Online:2016-02-01 Published:2016-02-03



  1. 太原理工大学 计算机科学与技术学院,太原 030024

Abstract: The current R-tree spatial clustering algorithms use a predefined k-value for clustering, and choose the initial clustering centers arbitrarily. The clustering results are easily dominated by the initial k-value and the outlier data. In order to solve these problems, this paper proposes a novel spatial clustering algorithm called DKSC (dynamical k-value spatial clustering algorithm), which dynamically determines the optimized k-value when constructing the tree. By choosing an optimized k-value, the algorithm allows the spatial data in the same subspace to be organized into the same sub-tree, and builds an efficient R-tree layer by layer from the root to leaves. The experiments conducted with real and simulated datasets show that the proposed algorithm can build optimized R-tree spatial indexes and improve retrieval efficiency.

Key words: spatial data, R-tree, spatial index, clustering algorithm

摘要: 目前采用的R-树空间聚类技术使用指定k值的聚类算法,初始聚类中心随机或指定选取。这样聚类的结果受初始k值影响,且易受离群空间数据的干扰。为解决上述问题,根据空间数据分布的特点,提出了动态确定k值的空间聚类算法(dynamical k-value spatial clustering algorithm, DKSC)。该算法通过聚类划分空间数据,把同一子空间的数据组织在同一个子树下,从根节点到叶子节点逐层构建R-树,形成高效的R-树空间索引。分别用真实和模拟的空间数据集进行了实验,结果表明该算法优化了构建的R-树空间索引,且具有更高效的查找效率。

关键词: 空间数据, R-树, 空间索引, 聚类算法