Abstract: This paper presents a quick speed spatial index structure based on R-link tree. And K-means algorithm in the structure is used. In K-means algorithm, value-standard deviation is adopted to ascertain the initial clustering centres to improve convergence speed and ultimate K value is ascertained by distance criterion function to make K value most suitable. The structure sometimes consumes more storage than R-link but gains better performance. Furthermore, the more data quantities, the better this kind of structure’s overall performance is.

Key words: spatial database, R-link tree, quad-tree, spatial clustering, spatial index

摘要： 提出基于R-link树的快速空间索引结构，在该结构中引入K-means算法。在K-means中采用均值-标准差确定初始聚类中心，提高了收敛速度。通过距离准则函数来优化K值，避免K值的盲目选取。与R-link相比空间开销代价有时略大，但换取了更高的性能，且数据量越多，索引结构的整体性能越好。

关键词: 空间数据库, R-link树, 四叉树, 空间聚类, 空间索引

CLC Number: 

• TP301.6