基于动态窗口的轮廓查询技术

时间:2024-02-14 点赞:43413 浏览:82970 作者原创标记本站原创

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

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

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

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会议上,DonaldKosann等人提出.它利用最近邻查询的结果来递归划分数据空间,分别求得轮廓.最近邻方法的查询速度比前几种方法都快,但是对于高维数据来说,该方法存在严重的空间重合问题.

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

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进行搜索了,只要对矩形DCEF进行搜索即可.那么就以点h(点D)为查询窗口的一个顶点对矩形DCEF进行搜索,采用相同的方法不断修剪查询空间.

对于每一个查询到的轮廓上的点p来说,都对应着一个有效区域V,这个有效区域V就是以点p为左上角顶点的区域.如图3所示,点p是刚查询到的轮廓点,阴影区就是点p对应的有效区,接下来要查找的轮廓点都在这个有效区V内.因为区域A内的空间数据点已经经过查询判断,区域B内的点全部被点p支配,所以只有区域V是轮廓点所在的区域.这样就只对这点p的有效区进行查询,不必对整个空间进行查询.

2.2.2算法描述

算法说明和分析中用到的符号表示如下:

S表示空间数据点集;p表示空间数据点集s中的数据点;L表示轮廓列表;Li表示轮廓列表中第i个轮廓点;Pn表示第n个查询窗口;VU表示查询窗口上边界的速率;VB表示查询窗口下边界的速率,VR表示查询窗口右边界的速率;N表示MBR构成的中间结点;q.length表示查询窗口q的长度;q.width表示查询窗口q的宽度;p.x表示数据点p的x坐标;p.y表示数据点p的x坐标和y坐标.

基于动态窗口查询的轮廓查询算法具体描述如下[11]:

2.2.3算法分析

基于动态窗口查询的轮廓查询算法将单个轮廓查询转换为多个不同的动态窗口查询,只有查询窗口的右边界是移动的,其他边界都是静止的.算法仅需要对有效区内的空间数据点进行查询,无须对整个空间的数据点进行搜索查询,有效地减少了查询空间,被访问点的数量明显减少.

查询窗口只访问轮廓点和与轮廓点具有部分相同坐标的点,并且每个数据点只访问一次.被查询窗口检索到数据点不一定就是轮廓点,需要根据其坐标情况进一步的判断才行.被检索到的数据点主要有下面3种情况:

1)有多个数据点同时落入查询窗口中,即这些数据点具有相同的x坐标.如图4所示.

图4情况1多个数据点落入查询窗口

图5情况2落入查询窗口的数据点与轮廓点部分坐标相等

2)新落入窗口的数据点与上一个插入到轮廓列表L中的轮廓点具有相同的y坐标,根据轮廓的支配定义可知,新点被支配,不是轮廓点,所以将新点删除.如图5所示.

3)落入查询窗口但又不满足前两个条件的数据点肯定是轮廓上的点,将其加入轮廓列表L中.

3基于动态窗口轮廓查询技术设计与实现

下面举例对基于动态窗口查询的轮廓查询算法对人员管理信息系统中的数据对象(静态数据对象)进行轮廓查询,详细分析并说明其具体查询过程.

假设有空间数据点集S,S等于{a,b,c,d,e,f,g,h,i},空间数据点的坐标分别为a(1,9),b(2,10),c(4,8),d(6,7),e(10,8),f(7,5),g(5,6),h(4,4),i(3,2),j(10,4),k(9,1),m(6,2),n(8,3)分别表示流动人员暂住地、流动人员工作地、发现流动人员位置、执法人员固定执勤点、发现大量流动人员位置、执法人员流动执勤点、临检人员、临检固定点、临检发现流动人员处、执法单位驻地、地方政府所在位置、临检流动点,如图6所示.

根据这些点,生成其MBR如图7所示.

假设所有空间数据点都在坐标系的第一象限中,建立坐标系.设轮廓点集为L,查询过程:首先轮廓点集L

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

设为Φ,生成一个查询窗口q,查询窗口的一个顶点在原点0,其长q.length是与y轴距离最近的MBR到y轴的距离,其宽q.width是与x轴距离最远的MBR到x轴的距离,如图8所示.当前检索到点a落在查询窗口内,将点a插入L中,L等于{a}即首先检索到的是流动人员暂住地,并成为首个轮廓点.

然后查询窗口q改为以点a为一顶点,其宽q.width是-‖a.y‖,其中‖a.y‖表示点a到x轴的距离,负号表示y轴负方向的长度,这样点a是查询窗口的左上角顶点.相反,正号表示y轴正方向的长度,那么点a就是查询窗口的左下角顶点.查询窗口q的长q.length由0开始不断增加,直到查询到中间输入,并且有空间点落入查询窗口中.如图9所示,点i落入查询窗口,i.y≠a.y,则将点i插入L中,L等于{a,i}即临检发现流动人员处成为轮廓点.

接着,查询窗口q改为以点i为一顶点,其宽q.width是-‖i.y‖,其长q.length由0开始不断增加,直到有空间点落入查询窗口中.如图10所示,点m落入查询窗口,m.y等于i.y,因为点m被点i支配,则点m不插入到L中,所以L等于{a,i}.继续查询窗口q改为以点m为一顶点,其宽q.width是-‖m.y‖,其长q.length由0开始不断增加,直到把空间点落入查询窗口中.如图11所示,点k落入q中,k.y等于i.y,将点k插入L中,L等于{a,i,k}即地方政府所在位置成为第3个轮廓点.

按照上面的方法继续执行,当查询窗口到达MBR的右边界时,结束查询.如图12所示,查询结束,最终结果L等于{a,i,k}.

图13是查询所得的轮廓,轮廓上有数据点a,i,k即流动人员暂住地、临检发现流动人员处和地方政府所在位置3个空间位置为轮廓点.

综上所述,窗口查询扫过的区域如图14阴影部分所示,空间直线右上侧的点不在查询范围内,所以在查询过程中不必对它们进行访问,从而大大减少结点访问数.


【参考文献】

[1]BorzsonyiS,KosannD,StockerK.TheSkylineOperator[C].ICDE,2001.

[2]TanK,EngP,OoiB,EfficientProgressiveSkylineComputation[C].VLDB,2001.

[3]KosannD,RamsakF,RostS.ShootingStarsintheSky:anOnlineAlgorit-hmforSkylineQueries[C].VLDB,2002.

[4]YuJing,LiuXin,LiuGuo-hua.AWindow-basedAlgorithmforSkylineQueri-es[J].ComputerSociety,2005,9.

[5]StojmenovicI,MiyakawaM.AnOptimalParallelAlgorithmforSolvingtheMaximalElementsProbleminthePlane[J].ParallelComputing,1988,7.

[6]MatousekJ.ComputingDominancesinEn[C]//informationPro-cessingLetters,1991,38.

[7]RoussopoulosN,KellyS,VincentF.NearestNeighborQueries[C].SIGMOD,1995.

[8]HjaltasonG,SametH.DistanceBrowsinginSpatialDatabases[C].ACMTODS,1999,24.

[9]KosannDRostSRostS.ShootingStarsintheSky:anOnlineAlgorithmforSkylineQueries[C].VLDB,2002.

[10]WangWei-ping,LiJian-zhong,ZhangDong-dong,GuoLong-jiang.SlidingWi-ndowBasedMethodforProcessingContinuousJ-AQueriesonDataStreams[J].JournalofSoftware,April2006.

[11]刘国华,等.数据库新理论、方法及技术导论[M].电子工业出版社,2006.

[责任编辑:汤静]

相关论文

计算机数据库信息查询技术

为您写数据库毕业论文和职称论文提供数据库类有关开题报告范文,与计算机数据库信息查询技术相关论文范文例文,包括关于数据库及计算机及数据。

计算机数据库信息查询技术

本文是一篇数据库论文范文,关于数据库相关毕业论文题目,关于计算机数据库信息查询技术相关函授毕业论文范文。适合数据库及计算机及数据方面。

数据库模糊查询技术应用

本文是一篇计算机论文范文,计算机相关硕士毕业论文,关于数据库模糊查询技术应用相关毕业论文提纲范文。适合计算机及数据库及信息工程方面的。

动态系统计算机电源仿真技术

本文是一篇计算机论文范文,计算机方面有关电大毕业论文,关于动态系统计算机电源仿真技术相关毕业论文格式范文。适合计算机及计算机仿真及模。

Lucene的查询技术

本文是一篇数据库论文范文,数据库方面有关毕业论文,关于Lucene的查询技术相关硕士学位毕业论文范文。适合数据库及信息检索及参考文献方面的。

动态网页开发技术探析

这篇嵌入式论文范文属于电子商务免费优秀学术论文范文,关于嵌入式方面硕士学位论文,与动态网页开发技术探析相关电子商务物流论文提纲。适合。

SQLServer查询优化技术与实现

这篇数据库论文范文属于参考文献免费优秀学术论文范文,数据库类在职研究生毕业论文,与SQLServer查询优化技术与实现相关论文参考文献自动生。