数据库有关论文范文检索,与基于动态窗口的轮廓查询技术相关论文的格式

本论文是一篇数据库有关论文的格式,关于基于动态窗口的轮廓查询技术相关硕士论文范文。免费优秀的关于数据库及轮廓及窗口方面论文范文资料,适合数据库论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

【摘 要】本文通过对几种轮廓查询技术的比较,选择基于动态窗口的轮廓查询技术作为研究对象,对其算法思想、算法描述和算法分析进行了详细的阐述,并结合流动人员管理信息系统对其进行了具体的设计与实现.

【关 键 词】动态窗口；轮廓查询技术

1轮廓查询技术研究现状

空间数据库系统是描述、存储和处理空间数据及其属性数据的数据库系统.空间数据库是随着GIS的开发和应用而发展起来的数据库新技术.它不是独立存在的系统,而是与应用紧密结合,通常是GIS的核心.空间查询优化是空间数据库相关技术研究的难点和突破点,轮廓查询技术已经成为空间查询及优化领域的热点课题.“轮廓”（Skyline）这个概念最初是2001年Borzsonyi等人在VLDB（VeryLargeDatabases）会议上作为一个操作被提出来的.由于轮廓查询技术有着重要的理论研究价值和实际应用价值,所以一直是相关领域专家们的研究重点.下面分别介绍国内外的研究成果.

D&C（Divide-and-Conquer）分治轮廓查询方法[1],2001年ICDE（InterationalConferenceonDataEngineering）会议上,Borzsonyi等人提出.该方法将数据集划分成多个分区,然后利用主存算法来分别计算每个分区内的局部轮廓,最终的轮廓通过将局部轮廓筛选并获得.该方法仅对小数据集有效.因为,如果整个数据集符合内存大小,那么仅需要应用一次主存轮廓算法即可.对于大数据集,分区的过程就需要至少一次读和写整个数据集,因此,导致严重的I/O代价.这种方法不适合在线处理,因为它不能在分区阶段完成之前返回任何轮廓点.

BNL（BlockNestedLoop）块嵌套循环轮廓查询方法[1],2001年ICDE会议上,Borzsonyi等人提出.这种方法就是基于这个思想扫描数据文件,在主存中保存一个轮廓点的候选列表,开始的时候列表中包含第一个数据点,随后的点p分3种情况：

（1）如果p被表中的任何一个点支配,那么p会被删除,它不是轮廓的一部分.

（2）如果p支配列表中的任何点,那么p将被插入列表中,并且列表中所有被p支配的点都将被删除.

（3）如果p既不被支配,也不支配列表中的点,那么它将被插入到列表中,它有可能是轮廓的一部分.

BNL的一个问题就是列表可能变得比主存还要大,当这种情况发生时,所有溢出的数据点都被添加到一个临时文件中,这就需要多次执行BNL.BNL的优点就是它广泛的应用性,因为它无需索引或将数据文件排序就可以应用到任意维上.BNL的主要问题就是对主存的依赖和在渐进处理方面存在缺陷.

位图轮廓查询方法（Bitmap）[2],2001年VLDB会议上,Tan等人提出.将所有的信息在位图中编码来确定一个点是否在轮廓上.位图法的效率依赖于位图操作的速度.这个轮廓的计算是昂贵的,因为对于每一个要检测的数据点,必须检索所有点的位图来得到对应位.如果不同值的数目非常大,那么,空间代价可能会很高.而且这种方法不适合动态数据集.

NN（NearestNeighbor）最近邻轮廓查询方法[3],2002年VLDB会议上,DonaldKossmann等人提出.它利用最近邻查询的结果来递归划分数据空间,分别求得轮廓.最近邻方法的查询速度比前几种方法都快,但是对于高维数据来说,该方法存在严重的空间重合问题.

SFS（SortFilterShyline）排序过滤轮廓查询方法,2003年ICDE会议上,Chomicki等人提出了BNL的改进方法.根据一个优先选择函数首先对整个数据集进行排序,候选点按照分值以升序插入到列表中,因为具有低分值的点可以支配大量的点,因此,使得修剪更有效.SFS展现出渐进的特点,因为数据的预排序能够确保支配点p’的点p必须在p’之前被访问,因此,能够立即将插入到列表中的点作为轮廓点进行输出.然而SFS不得不扫描整个数据文件才能返回一个完整的轮廓.

BBS（BranchandBoundSkyline）分支限界轮廓查询方法,2005年TODS（TransactionsonDatabaseSystems）会议上,D.Papadias等人提出.它与前面的最近邻轮廓查询方法类似,采用分支限界矩形图,通过深度优先遍历算法来进行轮廓查询,该方法没有考虑到用户后期筛选计算的方便性,缺少一定的实际应用性,不能很好地满足用户的需求.

以上几种轮廓查询技术的比较如表1所示.

基于以上分析,本论文将采用基于动态窗口的轮廓查询技术,可以较好解决以上查询方法存在的缺陷.

2动态窗口轮廓查询技术

2.1空间数据库轮廓查询示例

在d维空间中,轮廓是一个d维点的集合,点集合是由在所有维上不被其它任何一个点支配的点组成.假定一个点的集合P1,P2,等,Ps,点Pi支配点Pj当且仅当点Pi在任意轴上的坐标都不大于点Pj对应的坐标.查询结果返回所有的点Pm,Pm是不被任一个Pn支配的点.

轮廓在涉及多标准决策的应用中起着非常重要的作用.例如,在出行选择交通工具时,有火车和飞机可供选择,可是飞机价格比火车票贵一些,但乘坐火车花费路途时间又太长,如何选择适合自己最佳的方案,轮廓的计算可有效解决这样的问题.如图1所示：

用x轴来表示乘坐交通工具的价格,用y轴来表示路途花费的时间,两个坐标轴表示的事物不同,所以单位尺度表示的意义也不同.坐标系中的点表示花费的时间.

点a,b,c是最优候选集,这3个点不被空间中任何其它对象支配,其它的点相对这3个点不是费时长就是价格高或者二者都有,都不理想.点a时间相对来说长,有最长的时间但是价格低,点b时间相对a来说短一些,但是价格相对高一些,点c价格最高,但花时最少,根据用户自己的实际情况可选择不同的出行方式.2.2基于动态窗口查询的轮廓查询算法

2.2.1算法思想[4-10]

基于动态窗口查询的轮廓查询算法通过窗口查询q来访问所有轮廓点集合中的点,是将单个轮廓查询转换为多个不同的动态窗口查询,只有查询窗口的右边界是移动的.查询窗口不断变化来缩小查询空间,访问有可能是轮廓上的点,并且每个数据点只访问一次.不用访问空间对象集合中的全部数据点.

如图2所示,N1,N2是空间中的两个最小边界矩形（MinimumBoundingRectangle,MBR）,MBR是用来界定地图大小的,确保要查询的空间信息都在该范围内,MBR可人为设定,一般以地图的左下角和右上角标注.首先生成一个查询窗口q,窗口的长q.length是与y轴距离最近的MBR到y轴的距离,即q.length等于|0F|（0是原点）,其宽q.width是与x轴距离最远的MBR到x轴的距离,即q.width等于|AF|.搜索到点a和h在查询窗口q中,因为在查询窗口内只有空间数据点a和h,没有其它的点的横坐标小于点a和h,且h的纵坐标小于a的纵坐标,所以点h支配点a,点h是轮廓点的点.点h支配矩形ABCD内的数据点,因此矩形ABCD内的所有点肯定不是轮廓中的点,有可能成为轮廓中的点的数据点必定在矩形DCEF内,下一步就不必对矩形ABCD进行搜索

1 2 下一页

数据库有关论文范文检索,与基于动态窗口的轮廓查询技术相关论文的格式参考文献资料：

本科毕业论文提纲范文

成人自考本科条件

函授本科考研

本科生论文标准格式

汉语言本科专业

本科论文检测

本科论文大纲

电大本科自考

南京大学自考本科毕业论文格式

本科数学专业毕业论文