一种面向GIS的静态R-树数据组织方法
黄继先1,2, 鲍光淑1, 肖志强1, 林 剑3
(1.中南大学 信息物理工程学院,湖南 长沙,410083;
2.中南大学 地学与环境工程学院,湖南 长沙,410083;
3.湖南科技大学 地球空间信息科学研究所,湖南 湘潭,411201)
摘要: 针对GIS空间数据提出了一种基于空间聚类的静态R-树生成方法。该方法用典型点法进行静态R-树数据组织,用空间对象的最小约束矩形代替空间对象本身进行空间聚类计算,形成若干聚类,并以R-树的构建规则进行适当调整,同时通过改进R-树的一些性能指标如覆盖区域、重叠面积和边界周长等提高其查询性能。通过将该算法与其他静态R-树算法如Low_x算法、Hilbert R-树算法进行比较,论证了该算法的可行性。
关键词: 静态R-树; 空间聚类; 数据组织; 典型点法; 空间填充曲线
中图分类号:P208 文献标识码:A 文章编号: 1672-7207(2005)03-0491-05
A static R-tree data organization method for GIS spatial data
HUANG Ji-xian1,2, BAO Guang-shu1, XIAO Zhi-qiang1, LIN Jian1
(1.School of Info-physics and Geomatics Engineering, Central South University, Changsha 410083, China;
2.School of Geoscience and Environment Engineering, Central South University, Changsha 410083, China;
3.Research Institute of Geo-spatial Information Science, Hunan University of Science & Technology,
Xiangtan 411201, China)
Abstract: Aiming at GIS spatial data, a new static R-tree construction method was proposed in this article. By this method, R-tree data organization was implemented by typical points approach in which spatial objects were replaced with their minimum boundary rectangles, and some performance targets such as covering, overlapping and boundary perimeter were modified to improve its query efficiency. Compared with other static R-tree algorithms such as Low-x algorithm and Hilbert R-tree, this method is feasible.
Key words: static R-tree; spatial clustering; data organization; typical points approach; space filling curve
R-树分为动态R-树和静态R-树[1],是目前应用最广泛的一种空间索引结构[2-4],尤其在GIS领域,R-树具有非常重要的作用。一般来说,GIS空间数据操作的特点是:插入、删除操作相对较少,而查询则较频繁。因此,在对GIS数据建立R-树时,可将GIS的空间数据集看作已知,并在此基础上对数据集中的空间对象进行预先组织,将满足一定条件的空间对象置于同一个叶节点中;在生成叶节点层后,以各叶节点代表的矩形为新的空间对象,再生成上一层节点,直至生成根节点为止。这种生成算法同样是静态R-树生成算法,通过对数据集的全局最优化,与动态R-树相比有较大的空间利用率和较好的查询性能。
静态R-树的数据组织是一个典型的空间聚类问题,常采用空间填充曲线的方法来进行。不同的空间填充曲线具有不同的聚类特性,Hilbert曲线是目前聚类性能最好的空间填充曲线[5]。目前,常用的静态R-树生成算法有:基于行—序的Low-x R-树生成算法[6]、基于Hilbert顺序的Hilbert R-树生成算法等[7]。 这些静态R-树生成算法大多以空间对象中一个参考点的坐标值或Hilbert值等参数作为排序的依据。实际上,这种处理方法只能反映空间对象的位置信息,而忽略了空间对象本身的形状和大小等信息,这对于纷繁复杂的空间数据的处理显然不实用。在此,作者针对GIS空间数据提出了一种基于空间聚类的静态R-树数据组织方法,用空间对象的MBR(最小约束矩形)代替空间对象本身进行空间聚类计算,形成若干聚类,并以R-树的规则进行适当调整,同时对覆盖区域、重叠面积和边界周长等影响R-树性能的指标进行优化,逐层生成R-树各节点层,直至生成根节点为止。
1 基于空间聚类的静态R-树构建方法
R-树是A.Guttman[8]提出的一种空间索引结构,它建立在地物的最小约束矩形的基础上,可以直接对空间中占据一定范围的空间对象进行索引。设M为每个节点所能容纳的最大实体数,m为每个节点容纳的最小实体数,且2≤m≤M/2,则R-树须满足下列条件:
a. 根节点若非叶子节点,则至少有2个子节点;
b. 每个非根节点包含的实体个数介于m和M之间;
c. 所有叶子节点在同一层次。
动态R-树通过动态插入算法实现,而静态R-树则通过对数据进行预先组织来实现。B.Sotiris等[9]认为动态R-树的节点分裂是一个典型的聚类问题,并用k-均值算法实现了动态R-树的节点分裂。所以说,静态R-树的数据组织与空间划分问题是一个典型的空间聚类问题,即要求将空间位置上相距较近的对象在R-树中尽可能置于同一节点。
聚类是提高空间数据查询处理性能的一个非常有用的特性[10]。使用聚类技术,可将逻辑上相关的对象(这些对象被同一查询访问的可能性很高)存储在相同的磁盘页面。
基于空间聚类技术的R-树构建的基本原理是以空间距离为聚类统计量,用空间聚类方法对空间数据进行分类组织,将属于同一聚类的空间对象置于同一个叶节点中,在生成叶节点层后,以代表各叶节点的矩形为新的空间对象,再生成上一层节点,直至生成根节点为止。在各层结点的生成过程中,用R-树的规则对分类结果进行调整以满足R-树的要求,同时调整R-树各项性能指标参数,以提高其性能。
在设计空间索引结构时,需要考虑2个问题,即存储空间的有效利用率与信息检索的效率。针对是优先减少索引时间还是优先减少存储空间的问题,划分空间的策略可能不同[4]。在此,采用空间聚类的方法来划分空间,力求在提高空间检索效率的同时,尽量提高存储空间利用率。提高空间利用率的方法是尽可能提高磁盘页的利用率,即使R-树各节点的子节点个数尽量接近M;而要提高R-树的空间搜索能力,则应使非叶结点所对应的最小约束矩形之间相互重叠的区域尽可能小[11]。
设N为空间对象个数,m和M分别为R-树每个节点所能容纳的最小和最大节点数,其总体流程如图1所示。假设m=2,M=5,构建R-树的基本步骤如下:
a. 确定初始聚类数目。为尽可能提高R-树的空间利用率,设定初始聚类数为N/M。
b. 确定初始聚类中心。用典型点法[12]确立初始聚类中心点,并引入距离阈值避免其陷入局部解。
图 1 R-树构建流程图
Fig. 1 Structure flow chart of R-tree
典型点法是一种常用的空间聚类算法,它是利用空间点群之间的距离来寻找m个典型点位,将这些点位作为聚类的中心,根据空间点与这些典型点的距离,将点划归到最近的一类。
距离阈值在此为任意2个聚类中心点间距离的最小值,任意与其他聚类点间距离小于该阈值的点均不能作为初始聚类点。阈值可通过多次实验选取1个最佳值。用典型点法形成的初始聚类中心如图2所示。可见,当未加阈值限制时,聚类中心限于局部(见图2(a));当加了距离阈值进行限制时,所得的聚类中心具有全局性(见图2(b))。
c. 形成自然聚类(见图3)。将典型点法得到的分类结果作为初始分类,计算各子群的重心作为聚类的凝聚点,重新进行类的划分,得到一个逐步逼近的聚类方法;当重新聚类结果不变时,聚类结束,形成稳定的自然聚类(见图3(a))。
d. R-树节点层聚类调整。用R-树的限制条件对所形成的聚类结果进行优化调整,对每个聚类包含的对象个数以R-树每个节点所能容纳的最小、最大节点数为准则进行调整,同时优化R-树节点层性能,即调整R-树的各项性能指标,尽量减少各层的覆盖面积、边界周长与重叠面积(见图3(b))。
e. 将调整好的聚类结果作为R-树的叶子节点,并以该聚类结果重新作为空间对象,重复以上步骤,直到所得的聚类数小于M为止(见图3(c))。
f.形成R-树。
![]()
(a) 未加阈值限制的聚类中心; (b) 加入阈值后的聚类中心
图 2 用典型点法形成的初始聚类中心
Fig. 2 Initial clustering center by method
of typical points
![]()
(a) 形成自然聚类; (b) 节点数最小的聚类;
(c) 节点数最大的聚类
图 3 自然聚类与R-树中间层
Fig. 3 Natural clusters and medium tier
of R-tree
2 节点层优化
由R-树区域查询性能模型[13,14]可知,影响R-树搜索性能的因素有R-树节点面积、边界周长、节点数等。这里主要从节点面积、边界周长、节点数3个方面对R-树中层聚类进行优化,即尽量减少节点面积、边界周长和节点数。减少节点面积可从2个方面进行:减少覆盖面积与重叠面积。覆盖是指与该层节点有关的所有矩形的总面积,重叠是同时包含2个或多个节点中的总重叠面积。减少覆盖就会减少死空间的数量,并在搜索中降低误击的可能性;减少重叠将会减小多路搜索的概率。R-树的查询效率会因重叠区域的增大而大大减小。
a. 减少覆盖区域与边界周长。采用R-树性能影响因子节点面积和边界周长加权和的增量作为聚类统计量,对聚类结果进行重新划分与调整,减小MBR覆盖区域面积与周长,从而达到减少R-树各层节点的覆盖区域面积与周长的目的(如图3(b)和3(c)所示)。
b. 减少重叠区域面积。对聚类调整时,使用R-树性能影响因子节点面积和边界周长加权和的增量作为聚类统计量,对重叠区域的节点进行重新分配,使R-树性能影响因子节点面积和边界周长加权和的增量尽可能小,即各聚类MBR相互重叠区域面积尽可能小。
c. 减少节点数,使节点分裂数尽可能少。
3 实验结果
覆盖区域、边界周长和重叠区域是衡量R-树搜索性能的重要因素,对这些因素进行分析比较可以判断R-树性能的优劣。各静态R-树的数据组织如图4所示,实际空间数据集的R-树空间划分与数据组织如图5所示。可见,采用本文算法的数据组织无论是在覆盖区域、边界周长、还是重叠区域方面,都明显低于其他算法的数据组织,说明该方法具有优良的查询性能。
![]()
(a) 随机的200个点; (b) Low-x算法数据组织; (c) Hilbert R-树数据组织; (d) 基于空间聚类的数据组织
图 4 各静态R-树的数据组织
Fig. 4 Data organization of some kinds of static R-tree
图 5 实际空间数据集的R-树空间划分与数据组织
Fig. 5 Spatial partition and data organization of practical spatial data sets
4 结 论
基于空间聚类的静态R-树数据组织方法与其他静态R-树如Low-x R-树和Hilbert R-树相比,无论是在减少覆盖区域和边界周长,还是在抑制重叠区域等方面,都明显地优于其他算法,具有更好的查询性能。对于查询操作频繁的GIS数据来说,这种索引结构具有明显的优越性。
参考文献:
[1]陈晟. GIS空间数据库基础技术研究[D].长沙:国防科学技术大学信息与通信工程学院,1998.
CHEN Sheng. The research of GIS spatial database foundational technique[D]. Changsha: Institute of Electrical Science and Engineering, National University of Defence Technology,1998.
[2]Marcel K, Douglas B. High-concurrency locking in R-trees[A]. Daval U. Proceedings of the 21st VLDB Conference[C]. San Francisco: Morgan Kaufmann Publishers Inc, 1995. 134-145.
[3]Schreck T, Chen Z. Branch grafting method for R-tree implementation[J]. The Journal of Systems and Software, 2000, 53: 83-93.
[4]朱铁稳.基于均匀空间离散域对象的空间数据库关键技术研究[D].长沙:国防科学技术大学信息与通信工程学院,2002.
ZHU Tie-wen. The key techniques of spatial database based on regularly spatial discrete domains objects [D]. Changsha: Institute of Electrical Science and Engineering, National University of Defence Technology, 2002.
[5]Faloutsos C, Roseman S. Fractals for secondary key retrieval[A]. Silberschatz A. Proc of 8th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems [C]. New York: ACM Press, 1989. 247-252.
[6]Leutenegger S T, Lopez M A. The effect of buffering on the performance of R-trees[A]. Proc of 14th Int Conf on Data Engineering[C]. Washington DC: IEEE Computer Society, 1998. 164-171.
[7]Kamel I. Hilbert R-tree: an improved R-tree using fractals[A]. Bocca J B. Proc of the 20th VLDB Conf[C]. San Francisco: Morgan Kaufmann Publishers Inc, 1994. 500-509.
[8]Guttman A. R-tree: a dynamic index structure for spatial searching[A]. Smith D. Proc of 1984 ACM SIGMOD Int Conf on Management of Data[C].New York: ACM Press, 1984. 47-57.
[9]Sotiris B, Dieter P, Theodoridis Y. Revisiting R-tree construction principles[A]. Manolopoulos Y, Pavol N. Proc of the 6th East European Conf on Advances in Databases and Information Systems[C]. London: Springer-Verlag, 2002. 149-162.
[10]Song J W, Whang K Y, Lee Y K, et al. The clustering property of corner transformation for spatial database application[J]. Information and Software Technology, 2002, 44: 419-429.
[11]史文中,郭薇,彭奕彰. 一种面向地理信息系统的空间索引方法[J]. 测绘学报,2001, 30(2): 156-161.
SHI Wen-zhong, GUO Wei, PENG Yi-zhang. A spatial indexing method for GIS[J]. the Journal of Cartography, 2001, 30(2): 156-161.
[12]郭仁忠. 空间分析[M].武汉: 武汉测绘科技大学出版社,2000.
GUO Ren-zhong. Spatial analysis[M]. Wuhan: Press of Wuhan Technical University of Surveying and Mapping, 2000.
[13]Kamel I, Faloutsos C. On packing R-trees[A]. Bhargava B. Proc of 2nd Int Conf on Information and Knowledge Management[C]. New York: ACM Press, 1993. 490-499.
[14]Pagel B U, Six H W. Are window queries representative for arbitrary range queries?[A]. Hull R. Proc of 15th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems[C]. New York: ACM Press, 1998. 150-160.
收稿日期:2004 -08 -10
作者简介: 黄继先(1973-),女,湖南临澧人,博士研究生,讲师,从事GIS空间数据库、GIS系统二次开发等研究
论文联系人: 黄继先,女,博士研究生,讲师;电话:13787258204(手机); E-mail:jxhuang@mail.csu.edu.cn
