首页 >  硕士论文 > 计算机硕士毕业论文 >   正文

时间依赖路网中反向k近邻查询计算机处理技术研究与实现

添加时间:2018-07-08 18:53:20   浏览:次   作者:
专业论文资料, 搜索论文发表论文代写论文网为你解忧愁!详情请咨询我们客服。
获取免费的论文资料? 欢迎您,提交你的论文要求,获取免费的帮助

本文是一篇计算机硕士毕业论文,人和计算机交流信息使用的语言称为计算机语言或称程序设计语言。计算机语言通常分为机器语言、汇编语言和高级语言三类。如果要在计算机上运行高级语言程序就必须配备程序语言翻译程序(下简称翻译程序)。翻译程序本身是一组程序,不同的高级语言都有相应的翻译程序。(以上内容来自百度百科)今天为大家推荐一篇计算机硕士毕业论文,供大家参考。

 
第 1 章 绪 论
 
如今人们对出行的时间成本更加关注,而车辆的增多导致道路行驶时间与距离不成正比,因此,时间依赖路网中反向 k 近邻查询算法的度量单位由路径距离变成了行驶时间。一般情况下,行驶时间取决于交通环境和出发时间。例如,相同的路径,上下班高峰时段通常比非高峰时段需要花费更多的时间,因此,在时间依赖路网中的 k 近邻查询、反向 k 近邻查询、路径规划查询、最短路径查询越来越受到学者专家的关注,所以研究时间依赖路网中的反向 k 近邻查询具有重要的实际意义。本章首先从研究背景、研究意义、研究目的等方面对课题进行介绍;然后,给出了本文的研究思路并进行必要的分析说明;最后,对本文组织结构进行简要概括。
 
1.1 研究背景
近些年,随着电子通讯技术的迅速发展,传统的信息获取和数据处理方式已经不能满足现在人们日常生活需求。人们可以通过无线网络技术(例如 WiFi、4G、5G、蓝牙等)和地理定位系统(例如 GPS、卫星技术等)能够快速的获取和处理有关的位置信息,大大提高了人们的生活品质,同时扩大了人们的生活、工作空间。如今手机、个人电脑、ipad 等电子设备的快速发展,越来越多的人们在使用这些移动电子设备分享和处理数据资源,而传统的有线网络对人们生活的限制越来越小,移动计算和云计算相结合的时代正在到来,此时人们可以随时随地获取和处理信息。在移动计算环境中,人们经常需要获得他们所在的地理位置有关的数据信息,以便于获得相应的有关位置的服务。正是因为人们对地理位置有关信息的需求增加(如:道路导航信息、天气信息、公共交通信息、公共设施的位置等等),从而促进了许多的有关地理位置服务(Location Based Services,LBSs)的产生和发展。有关地理位置服务的查询被称之为相关位置查询(Location Dependent Queries,LDQ)。空间数据库是数据库的一个重要研究方向,而相关位置查询又是空间数据库中一种重要的查询类型。近年来,随着相关位置查询的应用范围越来越广泛,在国际上也引起了广泛的关注,相关位置查询越来越成为当前的一个重要研究课题。相关位置查询一直受到国际三大会(SIGMOD、ICDE、VLDB)的关注,并且将相关位置查询作为研究领域主体内容之一,为了给该领域的专家学者提供交流的机会,每年国际三大会都会收录有关该研究的优秀论文。目前在国内的单位已经开展研究相关位置查询的并不是很多,其中还是主要集中在科学院所(例如中科院等)或者著名的高校(例如复旦大学、北京理工大学等等)。但是,近几年来随着国内的科技以及基础设施的快速发展,相关位置查询也越来越关注,越来越多的机构和研究者投入了大量的人力和物力资源来从事该领域的研究。反向 k 近邻查询是相关位置查询的一种重要的查询类型。相关位置查询查询包含多种查询类型:范围查询、最近邻(Nearest Neighbor,NN)查询、反向最近邻(Reverse NearestNeighbor,RNN)查询、k 近邻(k Nearest Neighbor,kNN)查询、反向 k 近邻(Reverse k NearestNeighbor,RkNN)查询、路径规划查询[1-5]、最短路径查询[6-10]等等。其中相关位置查询中最为传统的一种查询类型是 NN 查询,而 kNN 查询是 NN 查询的一种扩展形式。NN查询和 kNN 查询在地理信息系统、生物基因研究等方面有着广泛的应用。反向最近邻查询是基于最近邻查询的一种新的查询类型,反向 k 近邻查询则是对反向最近邻查询的一种扩展形式。反向最近邻查询与反向 k 近邻查询在智能导航系统、决策支持系统等也有着广泛的应用。
..........
 
1.2 研究意义
近些年来,随着有关路网中查询技术的逐渐发展,越来越多的人关注时间依赖路网环境下的反向 k 近邻查询问题,特别是在动态环境下的反向 k 近邻查询技术,包括时间依赖环境下的反向 k 近邻查询、移动对象环境下的反向 k 近邻查询。 因此,研究空间数据库中的时间依赖环境下的反向 k 近邻查询具有重要意义,主要包括以下几个方面:随着数字化时代的到来,反向 k 近邻查询技术在救灾和战争中也发挥着越来越重要的作用。指挥人员可以利用地理信息定位系统等定位服务,用于确定救援人员、救援车辆、救援物资等的地理位置,及时获取相关的数据和信息,以便及时的提供救援服务,保证他们的救灾队伍能够在灾难救援或者战场中的主动性得到充分的发挥。例如,在战场上参战的医务兵想要知道他成为其他哪些士兵的 k 近邻之一,此时就是再执行一个反向 k 近邻查询操作,这样他就可以及时的为那些伤员提供救援帮助。然而如果查询后的结果出现错误,也就是说查询后结果的正确性不能够得到保证,这势必会造成很大的损失。决策支持系统在日常生活中同样拥有广泛的应用,比如如今市场竞争日益剧烈,某家超市需要做市场调研,调查超市需要在何地选址建立新的连锁店,新的连锁店给当地的哪些商家会造成影响,使得新的连锁店最具有影响力,力争占据更多的市场份额,这就需要超市执行一个反向 k 近邻查询操作,查询新的连锁店是否成为他们的 k 近邻之一作为判断依据。一旦查询结果受到影响,那么有可能会影响到公司未来的战略规划,甚至会直接造成经济上的损失。
;........
 
第 2 章 国内外相关研究现状分析
 
反向 k 近邻查询是空间数据库中一项重要的有关位置的查询技术,在 2000 年 F.Kom和 S.Muthukrishnan 等人[11]首次提出了有关反向 k 近邻查询的概念,随后反向 k 近邻查询就一直备受关注,而近些年来,时间依赖路网中的 RkNN 查询成为了反向 k 近邻查询中一项重要研究内容,相应的研究机构以及科研单位同时也投入了大量的人力、物力和财力,用于该领域的研究。高效的 RkNN 算法研究大多数集中在传统欧氏空间或者静态路网环境下,对于时间依赖路网中的 RkNN 查询研究比较少。而欧式空间或者静态路网中的度量单位与时间依赖路网中的度量单位是有差别的,在欧式空间中,对象之间的距离是对象间的相对位置;在静态路网中,对象之间的距离是对象间的路径长度;而在时间依赖路网中,对象之间的距离是沿着路径的行驶时间。由于时间依赖路网中边的权值随时间而动态变化,且查询结果依赖于用户出发时间,已有静态路网下的算法无法直接用来求解时间依赖路网下的各类路径相关的查询问题,亟待新的解决方法,因此 TD-RkNN 查询算法被提出。
 
2.1 空间数据库索引技术
时间依赖路网中反向 k 近邻查询是空间数据库中一种重要的有关位置的查询技术,如何对时间依赖路网中的数据实现快速的查询和获取操作,如点查询,区域查询等,通常需要采用空间数据库索引[12]技术,索引的建立能够快速定位时间依赖路网中选定的数据对象,以此来提高查询的速度和效率。对于时间依赖路网中反向 k 近邻查询技术大多采用多维空间索引方法。X-树试图解决当针对对象层次结构使用一个索引方法时找不到一个好的划分(即不会导致的交叉重叠)所遇到的一些问题。X-树是一个对象层次(例如一个用于处理高维点数据和空间数据的带扩展的 R-树)的变形。在 X-树中,如果节点分裂会导致很高程度的结果节点的交叉重叠,则应该避免分裂。具体来说,如果一个节点溢出而又找不到合适的分裂位置,则该节点会被扩大而占据两个磁盘块,这样的节点称之为超节点。超节点可以被进一步的扩大(没有合适的分裂位置时),所以超节点可能会占据任意数量的磁盘块。事实上,在极端的情况下,目录中只有一个超节点。
.........
 
2.2 k 近邻查询
 
2.2.1 静态路网中 k 近邻查询
最近邻查询技术,是 k 近邻查询技术的基础。非时间依赖路网中的 k 近邻查询技术研究,大都基于最近邻查询技术进行路网扩展,将查询过程分为过滤阶段和精确阶段两部分。对 k 近邻查询结果集进行安全区域维护,进而提出解决连续 k 近邻的查询技术。Tao 等人[13]结合 R 树和分支定界剪枝技术,提出连续最近邻和连续 k 近邻算法。通过做邻近圆进行剪枝,将落在圆内的兴趣点(Points of interest,POIs)作为最近邻。当不断前进时,结合 R 树检索,对邻近圆及间隔点更新,得到最近邻的安全区域。并将这种方法应用到连续 k 近邻查询中,但该算法仅适用于欧式空间,不符合实际路网特点,有很大的局限性。Papadias 等人[14]提出 IER 和 INE 算法,将欧式距离和路网信息结合,把欧式距离作为下限,路网距离作为上限,得到搜索区域的范围,有效减少了查找的搜索空间。并将该技术应用到 k 近邻查询,范围查询中。IER 在进行 k 近邻查询时,利用 R 树在欧式空间得到 N(N>K)近邻,并计算 N 近邻的路网距离,根据 N 近邻的路网距离进行排序,若 Pk 的路网距离为且值 DK 最大,则将 DK 设为路网扩展的上界。对路网进行扩展,当查询点到兴趣点 p 的欧式距离和路网距离都小于 DK 时,p 加入到候选集中,并跟新DK。直到欧氏距离大于路网距离时停止。当近邻的路网距离与欧式距离相差较大时,IER存在大量无用计算。因此,提出 INE 算法来进行 IER 的优化。虽然该算法解决了路网下的近邻查询,但在查询过程中 N 的值难以确定,并且对于低密度路网将导致算法效率急剧下降。
.........
 
第 3 章 基于网格划分的反向 k 近邻查询算法 mTD-SubG.......15
3.1 问题描述及相关概念......15
3.2 基于网格划分的 mTD-SubG 查询算法.......17
3.2.1 预处理阶段...........17
3.3.2 查询阶段.....19
3.4 本章小结......22
第 4 章 基于网格合并的 mTD-SubG-Imp 查询算法........23
4.1 mTD-SubG 算法分析......23
4.2 mTD-SubG-Imp 算法......25
4.2.1 mTD-SubG-Imp 算法预处阶段.........25
4.2.2 mTD-SubG-Imp 算法查询阶段.........26
4.3 本章小结......27
第 5 章 实验结果与分析.....28
5.1 实验环境与配置....28
5.2 mTD-SubG 算法的实现............28
5.3 实验结果与分析....31
5.4 本章小结......36
 
第 5 章 实验结果与分析
 
5.1 实验环境与配置
为了验证本文所提出的 mTD-SubG 算法与改进的 mTD-SubG 算法的性能,实验中将其与 F Borutta 等人提出的 mTD-Eager 算法进行了比较,本文将改进的 mTD-SubG 算法成为mTD-SubG-Imp算法。算法使用Java语言实现,实验环境设置为Intel(R) Core(TM)i5-3470 CPU @3.20GHz,4G 内存,1T 硬盘,64 位 Windows 操作系统。实验用德国奥尔登堡的路网图,进行仿真实验,地图含有节点 6105 个,边 7035 条。实验中的兴趣点随机产生,并且均匀分布。本文将全天分为五个时段:[22:00,7:00)、[7:00,9:00)、[9:00,17:00)、[17:00,19:00)、[19:00,22:00) ,每隔五分钟对边赋一次权值,得到 288 个边的权值,根据这些边的权值拟合为分段线性函数,将该函数作为路网中边的权值函数。本文在预处理阶段利用网格划分技术,将整个时间依赖路网划分成为若干个大小相等的规则的网格,如图 5.1 表示为路网划分网格的操作界面,需要输入 min_X、min_Y、max_X、max_Y 等整个路网地图大小的参数,还需要输入网格划分大小的行数和列数。点击“确定输入”按钮后,完成整个时间依赖路网的网格划分。网格划分完成后,所形成的数据文件如图 5.2 所示。 其中,“每个网格包含的点数据”文件夹中保存了每个网格中的节点信息,如图 5.3 表示第 272 个网格中所包含的节点信息,其中包括了网格 ID、网格的边界节点 ID、网格中所有节点 ID、网格中所包含的 POIs 的 ID、以及网格中所包含的节点个数。“每个网格包含的边数据”文件夹中保存了每个网格的边信息,如图 5.4 表示第 272 个网格中所包含的边信息,其中包括了网格 ID、每条边的 ID 以及每条边的起点 ID 和终点 ID。
\
........
 
结 论
 
如今人们对出行的时间成本更加关注,车辆的增多导致道路行驶时间与距离不成正比,因此,行驶时间成为了时间依赖路网中反向 k 近邻查询算法中的度量单位,而不再是欧式空间中对象之间的相对位置或者静态路网中对象之间的路径长度。反向 k 近邻查询作为空间数据库中一项重要的查询操作,一直被广泛应用。然而分析了现有的关于反向 k 近邻查询方法后,发现目前的一些反向 k 近邻查询方法大多集中在欧式空间或者静态路网,对于时间依赖路网中的反向 k 近邻查询的研究相对较少。而已有的时间依赖路网中反向 k 近邻查询算法在兴趣点密度稀疏或者查询 k 值较大时,查询的响应时间较长,遍历节点的数量较多,整体的查询效率较低。因此,针对已有的时间依赖路网中反向 k 近邻查询算法在兴趣点密度稀疏或者查询k 值较大时查询效率低的问题,本文提出了基于网格划分的反向 k 近邻查询算法mTD-SubG。首先,将整个路网划分为大小相同的网格,通过网格的边界节点向其它网格进行扩展,加快对路网中兴趣点的查找速度;其次,利用剪枝技术缩小路网的扩展范围;最后,对查找到的兴趣点利用已有时间依赖路网下的近邻查询算法,判定其是否为反向 k 近邻结果。对于 mTD-SubG 算法的不足,本文同时提出了对 mTD-SubG 算法的改进算法 mTD-SubG-Imp 算法,mTD-SubG-Imp 算法在预处理阶段对不含有兴趣点的网格进行了合并处理,减少了在兴趣点密度稀疏或者网格划分范围过小的情况下,不含有兴趣点的网格之间的扩展,从而减少了查询的响应时间以及遍历节点的数量,提高了mTD-SubG 算法的查询效率。
..........
参考文献(略)

提供海量毕业论文,论文格式,论文格式范文,留学生论文,商务报告相关资料检索服务。
本论文由代写论文网整理提供 http://www.dxlwwang.com/
需要专业的学术论文资料,请联系我们客服
本文地址:http://www.dxlwwang.com/jsj/6747.html
论文关键字:计算机硕士毕业论文 处理技术