空间数据库中连接查询方法的研究

来源 :重庆邮电大学 | 被引量 : 0次 | 上传用户:dick_ust
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
空间数据库技术是当前数据库领域中的研究热点,在国内外的许多不同领域都得到了应用。由于空间数据库中的数据无序、庞大,以及空间对象与空间查询的高度复杂性,使得查询效率成为衡量空间数据库性能的重要指标,并且实际应用也对空间数据库的查询性能提出了迫切要求。   空间连接操作是空间数据库中的一种基本操作,同时它也是最耗时、最复杂的操作之一。在众多的空间连接方法之中,当两个数据集均建立R-树索引时,基于R-树的连接算法性能最佳。R-树空间连接算法根据遍历策略的不同有两种经典的算法,深度优先的R-树空间连接算法(Depth-First R-tree Join,DFRJ)和广度优先的R-树空间连接算法(Breadth-First R-tree Join,BFRJ)。后来出现的基于广度优先搜索的层内分组扫描策略的R-树空间连接算法(Breadth-First Group-based Sweeping,BFGS)就是基于BFRJ算法提出来的。BFRJ和BFGS算法都是效率很高的算法,但是这些算法对中间连接索引(Intermediate Join Index,IJI)进行排序时,并没有将中间连接索引的二元组的两个数据项进行充分考虑,没有考虑到空间相接近的对象它们重叠的对象也可能是相同的,这样就不能充分利用缓冲区中的数据。针对这样的问题,使用一种空间填充曲线(Adaptive Row Major Order,ARMO)对中间连接索引进行了排序。   首先,本文对基于R-树的空间连接算法进行研究,从广度优先策略的R-树空间连接算法的原理、特点和流程出发,分析中间连接索引优化排序对算法的重要性及对算法性能的影响。其次,本文基于BFRJ算法提出了一种对中间连接索引优化排序的空间连接算法(Optimal Breadth-First R-tree Join,OBFRJ)。该算法使用广度优先顺序对两棵R-树进行同步遍历,对生成的中间连接索引采用一种空间填充曲线进行排序,使得在下一层的连接时出现页错误的次数减少。最后,论文把OBFRJ算法同其它基于R-树的空间连接算法进行理论分析和比较,同时在开源的对象-关系数据库PostgreSQL8.3上实现了OBFRJ算法并且进行了相关的实验测试,通过实验表明,特别是在缓冲区较大时,改进的算法在CUP代价和I/O代价上都要小于BFGS算法,能够更好的满足查询的需求。  
其他文献
预测分类是数据挖掘中的一个重要的分支部分。它能够用来预测对象的数据标签。目前,数据分类技术在很多领域都有着广泛的应用,如银行中的风险评估,市场营销中的客户分类,文本检索
动态背景下运动目标的检测是计算机视觉领域的一个重要课题,在精确制导武器、交通监控、智能车辆等领域有着广泛的应用前景。研究由于摄像机运动引起的背景运动并检测其中的
电容层析成像技术(ECT)和电阻层析成像技术(ERT)都是基于电磁场理论的新型测量技术,具有广阔的应用前景。将两种技术融合成双模态成像技术,可以扩大应用范围,提高测量精度,成为过程层
近年来,无线传感器网络获得了快速发展,广泛应用于环境监控、医疗卫生、军事以及工业等领域,同时也引起了众多研究者的关注。WSN的覆盖问题是网络构建初期和应用过程中的必要
随着在创新2.0下“互联网+”这种新业态的出现,社会生活的各个领域都与互联网变得密不可分。这也导致了互联网上的各类非结构化数据,结构化数据,半结构化数据的大数据爆炸式
无线传感器网络融合了传感器技术、信息技术和网络通信技术,它是由大量传感器节点通过无线通信技术自组织构成的网络。无线传感器网络是信息技术中的一个新的领域,在军事和民用
随着P2P网络应用和用户数量的不断增加,网络所面临的问题比如网络拥塞和Qos保障等问题变得越来越棘手。因此,对P2P进行识别并加以控制就成了关键问题。早期的P2P应用通常采用
随着科学技术的发展,许多生产和科学研究领域对计算机的计算能力要求越来越高,传统的单处理器系统受散热问题和制造工艺等因素的影响已达到性能瓶颈,处理器体系结构开始向多核心
信息技术的急速发展在不断地改变人们生活方式的同时,也使得信息传播的形式在不断地丰富和翻新。短文本(通常文本长度小于160字符)作为手机简讯、在线即时聊天、论坛用户评论
为了适应业务带宽、服务质量以及网络覆盖等多方面需求,以及应对各种新的宽带无线接入技术对3G系统形成的挑战,3GPP组织于2004年12月启动了无线接入网LTE(Long Term Evolution,