论文部分内容阅读
摘要:R-Tree允许兄弟节点之间的相互重叠,具有多路查找的特点,而Hilbert R-Tree也不能有效降低子空间的相互重叠,直接影响查询效率。提出了一种基于混合聚类的空间索引算法,将K-means和K中心点引入索引结构,改变了经典K-means算法对初始聚类中心的随机选取,减少了叶节点的MBR面积和各个子空间的重叠。通过实验表明,该算法具有更快的响应速度和查询效率。
关键词:空间索引;混合聚类;Hilbert R-Tree;K-means;K中心点;空间查询
中图分类号:TP311文献标识码:A 文章编号:1009-3044(2009)35-10047-02
A Spatial Index Algorithm Based on Spatial Cluster Analysis
HAN Qiu-ying1, MA Jun1,2, ZHANG Shao-hui3
(1.College of Computer and Information Engineering, Henan University, Kaifeng 475004,China;2.Institute of Data and Knowledge Engineering, Henan University,Kaifeng 475004,China;3.Department of Computer Science, Zhoukou Normal University,Zhoukou 466000,China)
Abstract: The R-Tree spatial index structure was analyzed.There are overlap between brothers nodes and multi-path in search ,and Hilbert R-Tree can not effectively reduce the overlap, which is a direct impact on query efficiency. Based on hybrid spatial clustering algorithms, a spatial index algorithm used K-means algorithm and K-center algorithm is proposed, which improve the random choice of the initial centrists in the classic K-means algorithm and decrease the leaf nodes MBR area and overlap between interior nodes. Experiments show that the algorithm has the faster response speed and the higher query efficiency.
Key words: spatial index; hybrid spatial clustering; hilbert R-tree; K-means; K-center; spatial query
随着GIS(Geographic Information System,地理信息系统)研究和管理的范围不断扩大,精度不断提高,需要处理的数据量也不断激增。由于空间数据本身的复杂性,以及目前对海量空间数据快速查询的要求日益提高,当前GIS正面临着大数据量空间数据存储及管理的挑战。如何组织、检索这些海量数据是空间索引要解决的问题之一。与非空间数据不同,空间索引处理的数据是二维、三维甚至是多维的不规则数据,故空间数据库的开销一般要比关系数据库要大[1]。所以研究空间索引结构、寻求更高效的空间索引算法,引起了人们越来越多的关注和兴趣。
近年来,人们提出了大量的空间索引方法,如R-Tree及其变种R*-Tree、R+-Tree、四叉树、Quad-Tree、Grid索引等等。R-Tree是空间数据库中最流行的索引结构之一[2],但是在动态构建树时容易造成空间区域重叠大,以及产生大量的“死空间”(不包含空间对象的索引空间),检索效率不高。
聚类分析是提高空间索引性能的一个非常有效的方法。目前已有K-means、CURE、ISODATA等多种算法,这些算法多数依赖于初始解的选择。当初始解选择不好时,会影响聚类质量,降低空间检索效率,且这些算法执行结果与数据输入次序有关[3]。
Hilbert R-Tree是由R-Tree发展而来的,具有R-Tree的特征,通过对R-Tree和Hilbert R-Tree的结构进行比较和分析,提出了一种利用混合聚类技术和Hilbert R-Tree相结合的空间索引算法,降低了构造树的时间复杂度,缩短了计算时间,提高了查询效率。
1 R-Tree简介
R-Tree最初由Guttman在1984年提出的,它是B-Tree在K维上的自然扩展,是空间数据库中最常用的空间索引结构[4]。R-Tree是一种完全动态的层次数据结构,在叶子节点中包含指向实际数据对象的指针,插入、删除和查询可以同时进行,并且不需要周期性的索引重组。如图1所示的平面划分对应的R-Tree为图2。
R-Tree索引具有其它索引方法无法企及的优势:1)它按数据来组织索引结构。这使它具有很强的灵活性、可调节性,不须预知整个空间对象所在的空间范围就可以建立索引。2)由于它是由B-Tree在K维上的自然扩展,具有相似的结构和特性,能很好的和传统的关系型数据库融合,这也是国外很多空间数据库选择R-Tree作为空间索引的重要原因之一。但是R-Tree中当节点中记录项超过M(每个节点存贮的最多索引记录项)时,节点必须分裂,这种分裂往往会导致节点内的数据重新聚类,并导致索引数据重组,反而降低了效率。而且,R-Tree允许兄弟节点的之间的相互重叠,对于精确匹配查询,不能保证唯一的搜索路径。
2 Hilbert R-Tree简介
Hilbert R-Tree是利用Hilbert曲线将高维对象映射到一维中,并保存了大部分空间信息。它将空间对象根据位置相邻关系打包,形成MBR(MinimumBounding Rectangle, 最小外接矩形),再把这些MBR的中心映射到Hilbert曲线上并进行升序排列,然后将排列好的数据依次放入叶节点中,再按照各节点产生的时间顺序,自底向上建立高层的目录节点,最后就得到一棵的空间存储利用率几乎100% Hilbert R-Tree。地图显示时,空间中距离近的空间对象被一起读取显示的概率大于距离远的空间对象,所以,将距离近的空间对象物理上靠近存储,在查询过程中可以有效的减少数据操作范围,减少了计算机I/O读取外存的次数和寻道时间(I/O的存取单元是一个物理磁盘块),加快查询过程。因为Hilbert曲线具有优良的聚类性质,能获得比一般R-Tree更小的节点覆盖区域,因此具有更高的存储利用率。
3 基于混合聚类的Hilbert R-Tree的空间索引算法
R-Tree是一种高度平衡树,显而易见总节点数量越少,查询效率越高;从R-Tree的结构来看,让空间上靠近的空间对象拥有尽可能近的共同祖先,则R-Tree的查询效率越高;根据R-Tree的聚类特性,对固定数目的空间对象划分聚类个数越多,聚类的性能越好。根据这种思路,本文将K-means聚类算法和K中心聚类算法相结合,提出一种基于混合聚类的Hilbert R-Tree构造方法,将空间相近的点放入相近的叶节点内,从而提高Hilbert R-Tree查询效率。
3.1混合聚类算法
所谓聚类就是在设计空间数据库的存储结构时,将空间上相邻的和查询上有关联的对象存储在物理位置相邻的存储单元里,减少存取时间,提高查询效率。在构建Hilbert R-Tree之前对数据进行采用混合聚类算法处理,将空间上邻近的对象聚集到同一个聚类中,可以得到更小叶节点的面积,极大提高R-Tree的查询效率。K-means算法从N个数据对象任意选择 k 个对象作为初始聚类中心,而对于剩下的其它对象,则根据它们与这些聚类中心的距离,分别将它们分配给与其最近的聚类,然后再计算每个新聚类的聚类中心(即该聚类中所有对象的均值),不断重复这一过程直到标准测度函数开始收敛为止。选择适当的初始解可以获得较好的聚类效果,但是,K-means算法依赖于初始解的选择,我们引进K中心聚类算法。K中心法使用中心点定义原型,其中中心点是一组点中最有代表性的点,利用空间点群之间的距离找到典型点位作为聚类的种子对象,根据空间对象与典型点的距离,将剩余对象归到最近的聚类。我们用空间对象的MBR的中心点代替每一个空间实体,设定N为空间对象数,M为R-Tree中每个节点所能包含的最大实体数,m是每个节点包含的最小实体数,k为划分的聚类个数。
混合聚类算法如下:
1)设置k的初值为[N/M],k的取值范围[N/M]~[N/m];
2)根据K中心聚类算法选择k个对象分别赋给k个集合,作为这k个集合的初始聚类中心。将k个对象的中心作为k个集合的中心。
3)利用K-means算法,对剩余的每一个对象找到离它最近的聚类中心(该聚类中所有对象的均值),并将该对象分配到该聚类中,对调整后的新类计算新的聚类中心。
4)重复步骤2),3),直至所有空间对象完全分配到k个集合中。
5)计算标准测度函数,以覆盖面积,重叠面积作为评估指标。
6)选择标准测度函数值最小的划分聚类个数。
3.2基于混合聚类的Hilbert R-Tree索引生成算法
利用空间距离比较接近的空间对象的Hillbert码值的也比较接近,空间对象的MBR距离较小的Hilbert码值相差也较小的性质,直接对叶节点的MBR进行聚类,对非叶节点进行Hilbert码值聚类。
树的生成算法如下:
1)以数据MBR为中心,调用上面的聚类算法,得到k个聚类中心Ci(i=1,2,…,k)。
2)根据Hilbert 映射函数将二维或三维空间映射到一维空间上,求出各个聚类中要素MBR的Hilbert码值,并按照各自的Hilbert值升序排列。
3)对产生的k个聚类进行判别,如果聚类中包含对象个数不大于M,不作处理,自成一个叶节点。对于聚类中对象个数大于M的,求出聚类中实体对象MBR的Hilbert码值,从第一个开始,按照Hilbert码值依次分为各含M个数据的组(最后一个节点除外)。
4)按照各节点产生的时间顺序,自底向上生成Hilbert R-Tree。
4 结果测试
在相同的软硬件平台上,分别用两种算法执行同一组查询,实验选用东莞市地图数据库,对同样的水文测站数据进行了实验。查询的响应时间主要有两部分组成,一部分是读取与查询区域相交的节点所需时间;另一部分是CPU处理这些节点所需时间。与从外存访问一个节点的时间相比,CPU的响应时间可以忽略。假定没有缓冲区的条件下,把所需访问的节点装入全部内存,磁盘访问次数和节点的访问次数是相等的。由于Hilbert R-Tree具有很好的聚类性质,从高维到一维的线性映射的速度也很快,自底向上的建树次序也使并行处理成为可能,多个CPU可同时处理不同的数据。从表1可以看出,聚类后的算法节省建树的时间,建立索引耗时更少。
采用的混合聚类算法基本能够把实际空间中比较接近的点聚集在同一个聚类中,改进后的方法实现了将相近的点放入相同叶节点中而相距较远的点放入不同叶节点的目的,从而降低了叶节点的面积,尤其是当数据分布非均匀时,对稀疏和稠密区域的分别处理,稠密区域的对象聚集放置,稀疏的对象分散放置,查询性能提高明显。从表2可以看出,改进后的Hilbert R-Treee检索效率可以提高30%以上。
从图3可以看出,聚类后的算法较好的实现了空间对象的“空间聚类性”,查询过程中可以有效的减少数据操作范围,减少了查询时磁头的跳转次数,涉及更少的磁盘页,查询效率有明显提高。
5 结论
本文根据空间对象的特征,采用聚类思想对Hilbert R-Tree的算法进行了改进,将K-mean聚类算法和K中心聚类算法引入了Hilbert R-Tree中。实验表明,通过对Hilbert R-Tree节点数据的聚类,空间节点分布也比R-Tree更均匀,减少了需要搜索的路径以及磁盘访问次数,提高了查询效率。以后将进一步深入研究缓存对空间索引的影响。
参考文献:
[1] 过志峰,王宇翔,杨崇俊.空间数据索引与查询技术研究及其应用[I].计算机工程及应用,2002,23(1):11-13.
[2] 廖克,等.地球信息科学导论[M].北京:科学出版社,2007.
[3] Kanungo T,Mount D M,Netanyahu N S.An Efficient K-means Clustering Algorithm[J].Communications and Computer Sciences,2005,23(9):66-70.
[4] Gaede V, Oliver Gunther. Multidimensional Access Methods[J].ACM Computing Surveys,1998,30(2):170-231.
[5] Beckmann N,Kriegel H P,Schneider R,et al.The R*-Tree:An Efficient Robust Access Method for Points and Rectangles[C].Atlantic City,NJ:Proc. ACM SIGMOD Int.Conf.on Management of Data,1990:322-331.
[6] 顾军,吴长斌.常用空间索引技术的分析[J].微型电脑应用,2001(12):38-42.
[7] 张明波,陆峰,申排伟,等.R树家族的演变和发展[J].计算机学报,2005,28(3):290-292
[8] 何江,李志蜀,陈宇.一种基于R树空间索引技术的GIS数据索引方法[J].四川大学学报:自然科学版,2008,45(6):1342-1343.
[9] 刘彦斌.基于聚类分析的R-Tree空间索引[J].廊坊师范学院学报,2009,9(3):27-292.
[10] Tan Pangning,Steinbach M,Kumar V.Introduction to Data Mining[M].北京:北京人民邮电出版社,2006.
[11] 何小苑,闵华清.基于聚类的Hilbert R-树空间索引算法[J].计算机工程,2009,35(9):39-42.
关键词:空间索引;混合聚类;Hilbert R-Tree;K-means;K中心点;空间查询
中图分类号:TP311文献标识码:A 文章编号:1009-3044(2009)35-10047-02
A Spatial Index Algorithm Based on Spatial Cluster Analysis
HAN Qiu-ying1, MA Jun1,2, ZHANG Shao-hui3
(1.College of Computer and Information Engineering, Henan University, Kaifeng 475004,China;2.Institute of Data and Knowledge Engineering, Henan University,Kaifeng 475004,China;3.Department of Computer Science, Zhoukou Normal University,Zhoukou 466000,China)
Abstract: The R-Tree spatial index structure was analyzed.There are overlap between brothers nodes and multi-path in search ,and Hilbert R-Tree can not effectively reduce the overlap, which is a direct impact on query efficiency. Based on hybrid spatial clustering algorithms, a spatial index algorithm used K-means algorithm and K-center algorithm is proposed, which improve the random choice of the initial centrists in the classic K-means algorithm and decrease the leaf nodes MBR area and overlap between interior nodes. Experiments show that the algorithm has the faster response speed and the higher query efficiency.
Key words: spatial index; hybrid spatial clustering; hilbert R-tree; K-means; K-center; spatial query
随着GIS(Geographic Information System,地理信息系统)研究和管理的范围不断扩大,精度不断提高,需要处理的数据量也不断激增。由于空间数据本身的复杂性,以及目前对海量空间数据快速查询的要求日益提高,当前GIS正面临着大数据量空间数据存储及管理的挑战。如何组织、检索这些海量数据是空间索引要解决的问题之一。与非空间数据不同,空间索引处理的数据是二维、三维甚至是多维的不规则数据,故空间数据库的开销一般要比关系数据库要大[1]。所以研究空间索引结构、寻求更高效的空间索引算法,引起了人们越来越多的关注和兴趣。
近年来,人们提出了大量的空间索引方法,如R-Tree及其变种R*-Tree、R+-Tree、四叉树、Quad-Tree、Grid索引等等。R-Tree是空间数据库中最流行的索引结构之一[2],但是在动态构建树时容易造成空间区域重叠大,以及产生大量的“死空间”(不包含空间对象的索引空间),检索效率不高。
聚类分析是提高空间索引性能的一个非常有效的方法。目前已有K-means、CURE、ISODATA等多种算法,这些算法多数依赖于初始解的选择。当初始解选择不好时,会影响聚类质量,降低空间检索效率,且这些算法执行结果与数据输入次序有关[3]。
Hilbert R-Tree是由R-Tree发展而来的,具有R-Tree的特征,通过对R-Tree和Hilbert R-Tree的结构进行比较和分析,提出了一种利用混合聚类技术和Hilbert R-Tree相结合的空间索引算法,降低了构造树的时间复杂度,缩短了计算时间,提高了查询效率。
1 R-Tree简介
R-Tree最初由Guttman在1984年提出的,它是B-Tree在K维上的自然扩展,是空间数据库中最常用的空间索引结构[4]。R-Tree是一种完全动态的层次数据结构,在叶子节点中包含指向实际数据对象的指针,插入、删除和查询可以同时进行,并且不需要周期性的索引重组。如图1所示的平面划分对应的R-Tree为图2。
R-Tree索引具有其它索引方法无法企及的优势:1)它按数据来组织索引结构。这使它具有很强的灵活性、可调节性,不须预知整个空间对象所在的空间范围就可以建立索引。2)由于它是由B-Tree在K维上的自然扩展,具有相似的结构和特性,能很好的和传统的关系型数据库融合,这也是国外很多空间数据库选择R-Tree作为空间索引的重要原因之一。但是R-Tree中当节点中记录项超过M(每个节点存贮的最多索引记录项)时,节点必须分裂,这种分裂往往会导致节点内的数据重新聚类,并导致索引数据重组,反而降低了效率。而且,R-Tree允许兄弟节点的之间的相互重叠,对于精确匹配查询,不能保证唯一的搜索路径。
2 Hilbert R-Tree简介
Hilbert R-Tree是利用Hilbert曲线将高维对象映射到一维中,并保存了大部分空间信息。它将空间对象根据位置相邻关系打包,形成MBR(MinimumBounding Rectangle, 最小外接矩形),再把这些MBR的中心映射到Hilbert曲线上并进行升序排列,然后将排列好的数据依次放入叶节点中,再按照各节点产生的时间顺序,自底向上建立高层的目录节点,最后就得到一棵的空间存储利用率几乎100% Hilbert R-Tree。地图显示时,空间中距离近的空间对象被一起读取显示的概率大于距离远的空间对象,所以,将距离近的空间对象物理上靠近存储,在查询过程中可以有效的减少数据操作范围,减少了计算机I/O读取外存的次数和寻道时间(I/O的存取单元是一个物理磁盘块),加快查询过程。因为Hilbert曲线具有优良的聚类性质,能获得比一般R-Tree更小的节点覆盖区域,因此具有更高的存储利用率。
3 基于混合聚类的Hilbert R-Tree的空间索引算法
R-Tree是一种高度平衡树,显而易见总节点数量越少,查询效率越高;从R-Tree的结构来看,让空间上靠近的空间对象拥有尽可能近的共同祖先,则R-Tree的查询效率越高;根据R-Tree的聚类特性,对固定数目的空间对象划分聚类个数越多,聚类的性能越好。根据这种思路,本文将K-means聚类算法和K中心聚类算法相结合,提出一种基于混合聚类的Hilbert R-Tree构造方法,将空间相近的点放入相近的叶节点内,从而提高Hilbert R-Tree查询效率。
3.1混合聚类算法
所谓聚类就是在设计空间数据库的存储结构时,将空间上相邻的和查询上有关联的对象存储在物理位置相邻的存储单元里,减少存取时间,提高查询效率。在构建Hilbert R-Tree之前对数据进行采用混合聚类算法处理,将空间上邻近的对象聚集到同一个聚类中,可以得到更小叶节点的面积,极大提高R-Tree的查询效率。K-means算法从N个数据对象任意选择 k 个对象作为初始聚类中心,而对于剩下的其它对象,则根据它们与这些聚类中心的距离,分别将它们分配给与其最近的聚类,然后再计算每个新聚类的聚类中心(即该聚类中所有对象的均值),不断重复这一过程直到标准测度函数开始收敛为止。选择适当的初始解可以获得较好的聚类效果,但是,K-means算法依赖于初始解的选择,我们引进K中心聚类算法。K中心法使用中心点定义原型,其中中心点是一组点中最有代表性的点,利用空间点群之间的距离找到典型点位作为聚类的种子对象,根据空间对象与典型点的距离,将剩余对象归到最近的聚类。我们用空间对象的MBR的中心点代替每一个空间实体,设定N为空间对象数,M为R-Tree中每个节点所能包含的最大实体数,m是每个节点包含的最小实体数,k为划分的聚类个数。
混合聚类算法如下:
1)设置k的初值为[N/M],k的取值范围[N/M]~[N/m];
2)根据K中心聚类算法选择k个对象分别赋给k个集合,作为这k个集合的初始聚类中心。将k个对象的中心作为k个集合的中心。
3)利用K-means算法,对剩余的每一个对象找到离它最近的聚类中心(该聚类中所有对象的均值),并将该对象分配到该聚类中,对调整后的新类计算新的聚类中心。
4)重复步骤2),3),直至所有空间对象完全分配到k个集合中。
5)计算标准测度函数,以覆盖面积,重叠面积作为评估指标。
6)选择标准测度函数值最小的划分聚类个数。
3.2基于混合聚类的Hilbert R-Tree索引生成算法
利用空间距离比较接近的空间对象的Hillbert码值的也比较接近,空间对象的MBR距离较小的Hilbert码值相差也较小的性质,直接对叶节点的MBR进行聚类,对非叶节点进行Hilbert码值聚类。
树的生成算法如下:
1)以数据MBR为中心,调用上面的聚类算法,得到k个聚类中心Ci(i=1,2,…,k)。
2)根据Hilbert 映射函数将二维或三维空间映射到一维空间上,求出各个聚类中要素MBR的Hilbert码值,并按照各自的Hilbert值升序排列。
3)对产生的k个聚类进行判别,如果聚类中包含对象个数不大于M,不作处理,自成一个叶节点。对于聚类中对象个数大于M的,求出聚类中实体对象MBR的Hilbert码值,从第一个开始,按照Hilbert码值依次分为各含M个数据的组(最后一个节点除外)。
4)按照各节点产生的时间顺序,自底向上生成Hilbert R-Tree。
4 结果测试
在相同的软硬件平台上,分别用两种算法执行同一组查询,实验选用东莞市地图数据库,对同样的水文测站数据进行了实验。查询的响应时间主要有两部分组成,一部分是读取与查询区域相交的节点所需时间;另一部分是CPU处理这些节点所需时间。与从外存访问一个节点的时间相比,CPU的响应时间可以忽略。假定没有缓冲区的条件下,把所需访问的节点装入全部内存,磁盘访问次数和节点的访问次数是相等的。由于Hilbert R-Tree具有很好的聚类性质,从高维到一维的线性映射的速度也很快,自底向上的建树次序也使并行处理成为可能,多个CPU可同时处理不同的数据。从表1可以看出,聚类后的算法节省建树的时间,建立索引耗时更少。
采用的混合聚类算法基本能够把实际空间中比较接近的点聚集在同一个聚类中,改进后的方法实现了将相近的点放入相同叶节点中而相距较远的点放入不同叶节点的目的,从而降低了叶节点的面积,尤其是当数据分布非均匀时,对稀疏和稠密区域的分别处理,稠密区域的对象聚集放置,稀疏的对象分散放置,查询性能提高明显。从表2可以看出,改进后的Hilbert R-Treee检索效率可以提高30%以上。
从图3可以看出,聚类后的算法较好的实现了空间对象的“空间聚类性”,查询过程中可以有效的减少数据操作范围,减少了查询时磁头的跳转次数,涉及更少的磁盘页,查询效率有明显提高。
5 结论
本文根据空间对象的特征,采用聚类思想对Hilbert R-Tree的算法进行了改进,将K-mean聚类算法和K中心聚类算法引入了Hilbert R-Tree中。实验表明,通过对Hilbert R-Tree节点数据的聚类,空间节点分布也比R-Tree更均匀,减少了需要搜索的路径以及磁盘访问次数,提高了查询效率。以后将进一步深入研究缓存对空间索引的影响。
参考文献:
[1] 过志峰,王宇翔,杨崇俊.空间数据索引与查询技术研究及其应用[I].计算机工程及应用,2002,23(1):11-13.
[2] 廖克,等.地球信息科学导论[M].北京:科学出版社,2007.
[3] Kanungo T,Mount D M,Netanyahu N S.An Efficient K-means Clustering Algorithm[J].Communications and Computer Sciences,2005,23(9):66-70.
[4] Gaede V, Oliver Gunther. Multidimensional Access Methods[J].ACM Computing Surveys,1998,30(2):170-231.
[5] Beckmann N,Kriegel H P,Schneider R,et al.The R*-Tree:An Efficient Robust Access Method for Points and Rectangles[C].Atlantic City,NJ:Proc. ACM SIGMOD Int.Conf.on Management of Data,1990:322-331.
[6] 顾军,吴长斌.常用空间索引技术的分析[J].微型电脑应用,2001(12):38-42.
[7] 张明波,陆峰,申排伟,等.R树家族的演变和发展[J].计算机学报,2005,28(3):290-292
[8] 何江,李志蜀,陈宇.一种基于R树空间索引技术的GIS数据索引方法[J].四川大学学报:自然科学版,2008,45(6):1342-1343.
[9] 刘彦斌.基于聚类分析的R-Tree空间索引[J].廊坊师范学院学报,2009,9(3):27-292.
[10] Tan Pangning,Steinbach M,Kumar V.Introduction to Data Mining[M].北京:北京人民邮电出版社,2006.
[11] 何小苑,闵华清.基于聚类的Hilbert R-树空间索引算法[J].计算机工程,2009,35(9):39-42.