分区贪婪bt

—68—基于分区技术的静态R树索引并行计算技术周芹1,2,钟耳顺1,黄耀欢3(1.
中国科学院地理科学与资源研究所,北京100101;2.
中国科学院研究生院,北京100039;3.
中国水利水电科学研究院,北京100044)摘要:海量空间数据静态R树索引的加载时耗很大.
该文利用关系数据库的优势,以空间数据分区存储技术为基础,提出针对自上而下的贪婪分裂算法的静态R树并行加载方法.
该方法提高了海量数据批量加载效率,支持分区粒度的索引重建.
论证与实验结果表明,并行构建的R树在合理空间数据分区下可以获得更高查询效率.
关键词:空间索引;静态R树;分区;并行计算ParallelComputationTechniqueforStaticR-treeIndexBasedonPartitionTechnologyZHOUQin1,2,ZHONGEr-shun1,HUANGYao-huan3(1.
InstituteofGeographicSciencesandNaturalResourcesResearch,ChineseAcademyofSciences,Beijing100101;2.
GraduateUniversityofChineseAcademyofSciences,Beijing100039;3.
ChinaInstituteofWaterResourcesandHydropowerResearch,Beijing100044)【Abstract】Bulk-loadingofstaticR-treeindexformassivespatialdataistimeconsuming.
Thispaperutilizestheadvantageofrelationaldatabase.
AimingattheTop-downGreedy-Split(TGS)algorithm,itproposesparallelbulk-loadingmethodofstaticR-treebasedonthestoragetechnologyofspatialdata.
Thismethodacceleratesthemassdatabulkloadingefficient,andsupportstheindexrebuildofpartitiongrading.
ArgumentationandexperimentalresultsshowthattheparallelbuiltR-treehashigherqueryefficiencyunderreasonablespatialdatapartition.
【Keywords】spatialindex;staticR-tree;partition;parallelcomputation计算机工程ComputerEngineering第35卷第2期Vol.
35No.
22009年1月January2009·软件技术与数据库·文章编号:1000—3428(2009)02—0068—02文献标识码:A中图分类号:TP311.
13R树索引性能优良,被广泛用于原型研究和商用空间数据库系统,它是目前最流行、最成功的多维索引结构之一[1].
但在海量空间数据的管理过程中,存在R树构建时耗过大、数据更新效率低、全局索引维护困难等问题.
因此,本文针对静态R树加载过程良好的可并行性,采用并行计算技术并行化R树的构建过程,以提高索引构建效率.
利用大型商用数据库分区技术管理海量空间数据,在逻辑上保证数据的无缝存储,确保查询效率并从物理层次上提高海量空间数据及其索引的可管理性、可用性和性能.
1分区技术在空间数据库引擎中的应用1.
1分区技术数据库提供的分区功能可以提高许多应用程序的可管理性、性能和可用性.
在GIS领域,将商用关系数据库作为空间数据的容器,采用分区技术提高空间数据访问的性能需要合理确定分区字段.
在分区的基础上建立高效、易于管理维护的空间索引是成功应用分区技术的关键.
1.
2海量空间数据的高效存储1.
2.
1分区方案选择常见的分区方法包括范围分区、Hash分区、列表分区和组合分区.
空间数据的特殊性在于其空间特性,根据GIS应用的特点,范围分区和列表分区较适合海量空间数据的大表分区存储.
本文采用范围分区方法,通过预先设定图幅范围避免范围分区带来的各分区数据不均匀问题.
1.
2.
2数据装载为保证分区内空间对象地理范围的连续性,先根据数据的空间分布特征划分图幅范围,各图幅应该是整个数据范围的一个划分.
如图1所示,根据数据的空间分布情况,将数据分为4个区,尽量保证各区数据量均衡.
存储在数据库中4个不同的表空间内,跨图幅的数据单独存放在分区4中.
0123分区1分区2分区3分区0分区4图1空间数据分区存储1.
2.
3数据维护基于分区技术的空间数据存储使空间数据能以分区为单位被维护并管理,如数据更新、索引维护等工作可以在单个分区内进行,而不影响其他分区中的数据,提高了海量数据的可管理性和可维护性.
作者简介:周芹(1982-),女,博士研究生,主研方向:GIS软件技术;钟耳顺,研究员、博士生导师;黄耀欢,博士研究生收稿日期:2008-07-20E-mail:zhouq.
06b@igsnrr.
ac.
cn—69—2静态R树的并行构建2.
1存在的问题空间数据的R树构建[2]是CPU密集型计算,且涉及大量I/O操作,其时耗很大.
已有很多方法可以加速R树的构建,如PackedR树、HilbertPackedR树、Bercken'sBufferR树、Arge'sBufferedR树等静态R树,但针对海量数据的R树构建时间仍然不能满足实际应用的要求.
且全局空间索引维护困难,海量空间数据的R树索引会导致树深度增加,查询效率下降.
存在小部分数据"脏区"时,必须对全局数据重建空间索引.
针对以上问题,在空间数据分区存储的基础上对分区数据并行计算空间索引,减少索引创建时间.
在保证查询效率的同时,提高全局索引的可维护性.
2.
2基于TGS算法的R树并行构建2.
2.
1TGS算法Garcia等人于1998提出自上而下的贪婪分裂(Top-downGreedy-Split,TGS)算法,其特点是自上而下地递归构建R树.
在R树的递归分裂过程中,通常采用扫描线分割空间中N个对象的MBR面积作为TGS的自定义代价函数选择扫描线,即f(r1,r2)=SArea(r1)+SArea(r2)其中,SArea(ri)为被扫描线分割的第i个部分的面积.
每次递归过程中选择分割当前子集中N个对象的MBR面积最小的扫描线,即S=min(fi(r1,r2))其中,i=1,2,…,n,n为扫描线总数;S为选取的扫描线;fi(r1,r2)表示第i条扫描线.
2.
2.
2R树的并行构建如图2所示,并行计算R树索引的基本思想如下:采用并行GIS处理常用的典型策略[3],即DCSO(Decomposition,Conquer,Stitch,Output)策略,本文数据分区存储实现了数据的自然分解,即问题分解;指定处理节点分别处理各分区数据,生成R树的子树;将各子树作为根节点的分支节点插入,完成整体索引创建,得到最终结果.
并行计算R树子树子树合并分区1分区2分区3分区0分区n0123n.
.
.
.
.
.
.
.
.
.
.
.
图2R树索引的并行计算2.
3查询效率分析R树的查询效率与节点的总面积和边长相关,在其他变量一定的情况下,总面积和边长越小,查询代价(磁盘I/O)越小[4].
在基于分区的R树索引的并行计算中,人为地在R树顶端对数据按分区范围生成n个分支节点,以提高数据的空间聚集度.
在保证数据量合理分区的情况下,R树节点将更趋近正方形,可以提高R树的整体质量和查询效率.
3实验结果3.
1并行计算平台的选择用集群实现并行计算具有很高的灵活性.
本文构建一个小型集群系统实现海量数据空间静态R树索引的并行计算.
3.
2实验环境4个计算节点硬件配置如下:Intel(R)Pentium(R)4CPU2.
60GHz,操作系统为MicrosoftWindows2000Professional.
一个数据服务器配置如下:Intel(R)Xeon(TM)CPU2.
40GHz,操作系统为MicrosoftWindows2003EnterpriseServerEdition,(05.
02.
3790.
00),数据库为Oracle10g.
单机串行计算实验结果如表1所示.
表1单机串行计算实验结果计算节点对象数计算时间/s节点115041101233.
5实验数据为全国1:250000等高线数据,共1504110条记录.
数据表分5个区存储,编号为0~4,其中,4区存储跨区对象.
集群计算实验结果见表2,其中,总时间包括数据传输、计算、数据存储的时间.
表2集群计算实验结果分区号对象数计算节点编号计算时间/s0286819090.
514191661120.
323270382108.
634695383150.
24154901.
2子树合并-00.
1总计--196.
53.
3实验结果及分析3.
3.
1索引构建时间对比采用TGS算法进行单机串行计算和集群计算的时间如下:4个节点进行并行计算获得的加速比为6.
28.
基于TGS算法的静态R树构建的计算量与数据量密切相关,对分区数据计算局部空间索引减少了计算量,因此,可以获得超线性加速比.
3.
3.
2查询效率对比采用上述算法构建的R树与串行构建的R树结构不同,根据2.
3小节的论述,比较2种方法所建立索引的叶子节点分布,如图3所示.
串行计算的索引包在数据密度较小的区域容易出现"长条"形状,通过分区方法能避免跨分区的"长条"出现,获得更好的查询效率,且R树结构将有所改善.
(a)串行计算结果(b)并行计算结果图3R树叶子节点对比在实际操作中对查询效率进行测试,由于点查询可以看作是域查询的特殊情况,因此本文采用域查询方式进行实验.
分别取图幅范围的1%,2%,3%,4%,5%作为查询窗口进行200次随机域查询,统计磁盘I/O数和查询时间,结果见图4、图5.
(下转第73页)—73—preupdatesdcswitcho{case:oAM==1STSTdbVOADsVOdcnndtdt←←=,STsVOdt←=AMRsrrDDUDPnaedep;case:oAS==1STSTdbVOADsVOdcnndtdt←←=,STsVOdt←=ASRsrrDDUDPnaedep;case:oMSE==2STSTdbVOADsVOdcnndtdt←←=,STsVOdt←=MSERsrrDDUDPnaedep;case:oSMTT==2STSTdbVOADsVOdcnndtdt←←=,STsVOdt←=SMTTRsrrDDUDPnaedep;case:oOOCT==2STSTdbVOADsVOdcnndtdt←←=,STsVOdt←=OOCTRsrrDDUDPnaedep;(2)grantsdcpermitaccesssoR→;(3)60)(.
5)oactivatesdcgrantsdcobsnsbnopreupdateobsnpreupdatesbnpreupdatesbt∧∧∧(.
))preupdatesstart,1preupdateobsnobsnobsn=+,1ooopreupdatesbnsbnsbn=+,0preupdatesbtsbt=,preupdatesstartsstartsysclock=;(4)sin_)(.
30)(.
))statesdcugdcsbtonupdatesbtonupdatesbtsbtsysclocksstart=;(5)((.
4)(.
30)sin_)osbnsbtstatesdcugdc≤(,))inactivatesdc;(6)inactivatesdcpostupdateobsn→,1postupdateobsnobsnobsn=;(7)((.
4)(.
30)sin_)osbnsbtstatesdcugdc(,))holdsdc;(8)holdsdcpostupdateobsn→;(9)0)(.
)orestoresdcholdsdcsbnpreupdateobsnopreupdatesbnpreupdatesbtpreupdatesstart∧∧;(10)sinsysclockUDstatesdcugdcrevokesdc(11)sysclockUDstatesdcgrantdcrevokesdc(12)sysclockUDstatesdcholddcrevokesdc(13)revokeaccesssorrevokesdc→;(14)activatesdcendaccesssor→;(15)revokeaccesssorendaccesssorpostupdatesdc∨→,postupdatesdcsdcnull=.
4结束语本文通过实例分析并展示改进模型的表达能力.
在有效使用期中,委托凭证只在主体第1次请求时产生,除非主体主动撤销,否则必须到有效使用期满时才会将其销毁.
在销毁前,委托凭证可以依据系统状态的变化转换到不同凭证处理状态.
参考文献[1]ParkJ,SandhuR.
TowardsUsageControlModels:BeyondTraditionalAccessControl[C]//Proceedingsofthe7thACMSymposiumonAccessControlModelsandTechnologies.
Monterey,California,USA:ACMPress,2002:57-64.
[2]ParkJ,SandhuR.
TheUCONABCUsageControlModel[J].
ACMTransactionsonInformationandSystemSecurity,2004,7(1):128-174.
[3]ZhangXinwen,Parisi-PresicceF,SandhuR,etal.
FormalModelandPolicySpecificationofUsageControl[J].
ACMTransactionsonInformationandSystemSecurity,2005,8(4):351-387.
[4]徐震,李斓,冯登国.
基于角色的受限委托模型[J].
软件学报,2005,16(5):970-978.
(上接第69页)05000100001500020000250003000012345并行串行图幅范围/(%)磁盘I/O数图4磁盘I/O对比05001000150020002500300012345图幅范围/(%)并行串行查询时间/ms图5查询时间对比由图4、图5可以看出,并行构建的R树,其磁盘I/O次数和查询时间均高于串行R树.
这是因为并行R树在构建之前人为地将图幅分区,使同一个分区的数据在R树中处于相对集中的索引包内.
当查询窗口落在分区内部时,搜索路径会相对减少,因此,提高了查询效率.
当查询窗口落在分区之间,最不理想的情况是查询窗口跨越4个分区,搜索路径会相对增加.
但各分区数据量的极度不均衡将导致各子R树深度不同,合并后的树不再是平衡树,查询效率将降低.
因此,R树的并行构建必须基于合理的数据分区,以保证并行计算时的负载平衡以及合并后R树的平衡.
4结束语R树索引的创建是并行度很高的计算过程,具体如下:按空间数据范围将数据分区存储后,对各分区进行并行处理,充分利用数据库的并发能力,提高并行计算过程中各子处理过程的数据访问性能,采用常用的DCSO策略,对结果进行合并输出.
参考文献[1]张明波,陆锋,申排伟,等.
R树家族的演变和发展[J].
计算机学报,2005,28(3):289-300.
[2]KamelI,FaloutsosC.
OnPackingR-trees[C]//Proceedingsofthe2ndInternationalConferenceonInformationandKnowledgeManagement.
Washington,D.
C.
,USA:[s.
n.
],1993.
[3]张立立.
海量地理空间数据的高性能计算[Z].
中国科学院地理资源与环境研究所,2005.
[4]TheodoridisY,SellisT.
AModelforthePredictionofR-treePerformance[C]//Proceedingsofthe15thACMSymposiumonPrinciplesofDatabaseSystems.
Montreal,Canada:ACMPress,1996:161-171.