并行空间连接查询处理

《并行空间连接查询处理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第36卷第4期上海交通大学学报Vol.36No.42002年4月JOURNALOFSHANGHAIJIAOTONGUNIVERSITYApr.2002文章编号:100622467(2002)0420512204并行空间连接查询处理刘宇,孙莉,田永青(上海交通大学自动化系,上海200030)摘要:基于顺序空间连接查询的效率不能令人满意,利用并行机制提高空间连接查询效率.空间连接查询的并行处理方法最重要的特征是任务分配根据多路平面扫描顺序,避免了连接处理过程中处理器之间的通信花费.提出基于空间连接花费模型的任务分配方法和基于花费估计的动态任

2、务分配策略,并给出了花费模型.该模型经实际应用效果明显.关键词:空间数据库;R树;多路空间连接;并行空间处理中图分类号:TP392;TP311文献标识码:AParallelSpatialJoinQueryProcessingLIUYu,SUNLi,TIANYong2qing(Dept.ofAutomation,ShanghaiJiaotongUniv.,Shanghai200030,China)Abstract:Oneofthemostimportantandtime2consumingtypesofqueryprocessingins

3、patialdatabasesisspatialjoin.Theresponsetimeofsequentialspatialjoinisfarfrommeetingtherequirementsofaninterac2tiveuser.Themostimportantcharacteroftheparallelprocessingmethodofspatialjoinqueryisthatthedistributionoftaskisbasedonplane2sweepingalgorithm,whichavoidsthecostof

4、communicationbetweenprocessorinthejoinprocessing.Thepaperputforwardthetask2distributingmethodbasedonspatialjoin,andthedynamictask2distributingstrategybasedoncost2estimation,andpresentedacostmodel.Theef2fectofthemodelisevidentinpractice.Keywords:spatialdatabases;R2trees;s

5、patialjoin;parallelqueryprocessing空间数据库中最重要的一种空间查询是空间连通过并行机制加速运行.然而,处理空间连接和处理接,即从两个或多个空间数据集合中检索出所有满自然连接是不同的,一些关系数据库的并行机制对足某一空间谓词(如交、包含等)的空间对象.由于空空间数据库不再适用.最近采用并行机制实施并行间对象的复杂性,通常空间查询分两步进行:过滤和空间数据库管理系统吸引了研究者的广泛关注.例[1][2]精简.首先根据空间索引产生满足条件的候选集,这如在Paradise工程中,Hoel等研究了基于相当于查询的

6、过滤步骤.然后通过精简步骤,从第2PMR四叉树的空间连接的并行处理,但他们的方法存储区检索每个对象的精确形状信息,测试其是否[3]是为特定目的平台而设计的.Kriegel等研究在无满足查询条件.共享和共享内存的混合结构上基于R树的并行空本文研究利用CPU和IöO并行机制来改进空间连接方法,提出空间并行查询的3个阶段:任务创间是连接处理的效率.对自然连接,显然,算法可以建、任务分配和并行任务执行,并讨论了缓冲区管理及一些任务分配策略.本文将平面扫描方法用于并行空间连接处理的收稿日期:2000206215作者简介:刘宇(1973-),男,新

7、疆伊犁人,博士生,研究方向:任务创建,并提出基于花费估计的动态任务分配策空间数据库,地理信息系统及其应用略,给出了花费模型.第4期刘宇,等:并行空间连接查询处理513动扫描线.假设扫描到第一个矩形为t,则t是1空间连接的并行处理Rseq∪Sseq中左下角坐标中最小的那个矩形.若t在尽管顺序空间连接处理性能不断得到改进,但Rseq中,从Sseq中找到一个矩形sh,使得shxi>txu,可空间连接还是耗时的操作,其响应时间远远超过了知对所有的j(1≤j

8、进一步判断,若Py(t)和Py(sj)也相交,则矩形t和空间连接.一般认为,并行连接查询由下面3个阶段矩形sj相交,将矩形t标记为已处理.接着,扫描下[3]组成:一个未经处理的矩形,直到全部矩形处理完毕;类