精选软件工程专业硕士论文范文篇一
第 1 章 绪 论
1.1 研究背景
空间数据库是数据库中一个非常重要的研究领域，其在交通网络系统、地理信息系统、生物基因研究、及决策支持系统等诸多应用领域中都有着广泛的应用。智能手机及 GPS 定位服务的出现使关于空间数据库的路网查询越来越普遍，从早期的系统[2][3][4]发展到现在，综合全面的地图定位匹配功能越来越稳定和成熟。谷歌、微软、苹果、百度以及国内外很多互联网公司也越发重视地理位置服务，以此来应对用户各种各样的查询服务需求，如最近邻查询(Nearest Neighbour , NN)，K 最近邻查询(K Nearest Neighbour , KNN)、反向最近邻查询(Reverse Nearest Neighbour , RNN)和反向最K最近邻查询(Reverse K Nearest Neighbour , RKNN)。如用户处在某个位置，想要查询距离他们最近的超市或者汽车加油站，这也就是最典型普遍的 k 最近邻查询(KNN 查询)[5][6]。也随之产生了很多 k 近邻查询变体，这些就涉及到距离的计算。由于我们日常的行动受限于道路网络的建设，所以任意两个位置的距离，即路网距离一定是大于等于这两个位置的欧几里得距离[5][6][21]或者基于最小距离的变体[34][35]、豪斯多夫距离[36]等。比如在一条双向行驶的高速公路上，给定一个用户的位置 q，一个加油站的位置 p，p 处于 q 所在公路的另一边。那么由 q 到 p 的路程代价即路网距离要远大于两个位置的欧几里得距离，因为用户不能直接开到高速公路的另一边逆向行驶，必须沿着高速公路规定的方向行驶。所以计算两点之间路网距离比欧几里得距离更有意义，从而基于路网的距离查询就变得非常有意义。但是两点之间路网距离的计算要比计算欧几里得距离所需的代价高，所以如何高效的在路网中进行距离查询是一个非常重要的问题。而现有的 k 近邻查询，大都是基于单个查询点的 k 近邻(简称单源 KNN)研究，少有的研究多源查询点的 KNN 大都是基于聚合距离，即查询对象到多个查询点距离的累积和最短的 Top-K。对于传统意义上的多源 KNN 研究，即到任意一个查询点距离最短的 Top-K 更是寥寥无几。仅有的 SILC 方法[1]是基于将所有点对间的最短路径预处理，虽然该算法采取了将最短路径巧妙压缩存储的方法，但仍耗费大量的内存空间，不适用于大的路网图。所以，本文针对此问题提出了基于内存的在线处理方法。
.....
1.2 研究现状
1973 年，唐纳德·克努特根据当时经典的邮局问题提出最近邻查询问题。最近邻查询是指在给定的空间数据集中，返回距离查询点最近的数据对象。例如我们之前举的例子，汽车在高速公路上查找距离自己最近的 K 个加油站。空间数据的海量性和空间数据库结构的复杂性导致空间数据的最近邻查询操作代价比较高，从而，对空间数据最近邻查询的改进优化成为国内外研究的重点问题。在路网上，基于单个查询点的 k 近邻查询（即单源 KNN）得到了很多的研究，分为在线计算[6]和预处理[37]42]两种类型的处理方法。也有结合关键字的空间单源KNN 查询[18]-20]。少有的研究多源查询点的 KNN 大都是基于聚合距离，如ANN(Aggregate Nearest Neighbour)[14]、 MANN(Merged Aggregate NearestNeighbour )[17]等，即查询对象到多个查询点距离的累积和最短的 top-k。而对于传统意义上的多源 KNN 研究，即到任意一个查询点距离最短的 top-k 更是寥寥无几，仅有的研究文献 SILC 方法[1]是基于将所有点对间的最短路径预处理，虽然该算法采取了巧妙的将最短路径压缩存储，但仍耗费大量的内存空间，不适用于大的路网图。所以本课题研究的主题是基于在线计算的多源 KNN 研究。而现有的跟本课题最相关的工作就是单源 KNN 查询，INE 算法是基于 Dijkstra 算法的思想，它访问路网结点是基于其距查询源点距离递增的顺序。它把遍历过的结点到查询点的距离都放入优先队列中，每次选取最小距离的结点来扩展它的邻接点。IER 算法先找到 k 个欧几里得距离最近的查询对象[23]，然后用最短路径算法逐个计算他们距查询点的路网距离，这 k 个查询对象形成了初始的候选集，然后依次不断的按照欧几里得距离找下一个近邻，用最短路径算法计算其距查询点的路网距离，更新候选集。
.....
第 2 章 基础知识概述
2.1 计算最短路径的基础算法
最短路径问题是在路网上查找某个结点到特定结点或其它所有结点的最短路径距离，它是路径查找方面的一个经典算法问题。计算最短路径的方法有很多，可依据情况分为以下几类：(1)确定起点的最短路径问题：即已知起始结点，求最短路径的问题。该情况适合于 Dijkstra(迪杰斯特拉)算法。(2)确定终点的最短路径问题：与已知起点的最短路径问题相反，该问题是已知终点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点问题。(3)确定起点和终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。该情况适合于 A*算法。(4) 全局最短路径问题：求图中所有结点之间的最短路径。该情况适合于Floyd-Warshall(弗洛伊德)算法。因本论文只涉及到第一种和第三种情况，所以，我们讲述一下 Dijkstra 和 A*算法的求解过程。
.....
2.2Dijkstra 算法
Dijkstra(迪杰斯特拉)算法是由荷兰计算机科学家艾兹格·W·迪科斯彻提出。用于解决单源最短路径问题，即查找路网图上某个结点到特定结点或其它所有结点的最短路径距离。Dijkstra 算法的基本思路是：从源点开始，运用贪心策略，从相邻的结点往外扩展找出到其它结点的最短路径，按路径长度递增的顺序求得到不同结点的最短路径。基本思想是：设置一个存放顶点的集合 S，并将源点放入到该集合，然后不断地扩充这个集合，当从源点到该结点的最短路径求出后则将该结点加入到集合 S 中。并更新从源点到集合 S 以外结点的当前最短路径距离，然后找出当前最短路径距离最小的结点，将其加入到集合 S，直到终点加入到 S 中。基本步骤如下：(1)把所有结点分成两个集合：集合 1 放入已经确定最短路径距离的结点；集合2 放入还未确定最短路径的结点。(2)初始化两个集合：集合 1 只放入源点，集合 2 则放入其余的结点。(3)运用贪心的思想，把集合 2 中结点按照当前最短路径长度递增的顺序依次加入到集合 1 中，并在每次加入后更新集合 2 中所有结点当前的最短路径距离，直到从源点可到达的所有结点都包含于集合 1 中。在整个过程中，不断更新当前的最短路径，始终保持从源点到集合 1 中每个结点的最短路径距离都小于或等于从源点到集合 2 中任意结点的当前最短路径距离。(4)直到所有结点都扫描完毕，即从源点可达的所有结点都已加入到集合 1 中，则得到从源点到其它各结点的最短路径距离。
......
第 3 章 基于逐一扩展的单源 KNN 方法 ....17
3.1 问题分析 .....17
3.2 基于逐一扩展的单源 Dijkstra 算法........17
3.3 基于逐一扩展的单源 IER 算法 ....22
3.4 本章小结 .....27
第 4 章 基于合并扩展的多源 KNN 方法 ....29
4.1 问题分析 .....29
4.2 基于合并扩展的多源 Dijkstra 算法........29
4.3 基于合并扩展的多源 IER 算法 ....32
4.4 本章小结 .....35
第 5 章 实 验.......36
5.1 实验环境 .....36
5.2 数据集和查询 .......36
5.3 评价标准 .....37
5.4 实验结果分析 .......37
第 5 章 实 验
5.1 实验环境
本文实验采用的数据集是真实的道路网络，表 5-1 显示的数据集为本实验所用的所有数据集，来源于表中描述了 5 个城市路网的结点数和边数，即路口个数和道路个数。这 5 个城市有大数据集城市代表，如旧金山、北美等。也有小数据集的代表，如奥尔登堡。通过对这 5 个城市的横向比较实验，可知本文算法在不同规模数据集下的性能，从而可以验证本文算法的可扩展性。注意，本实验只采用城市道路网络，而不采用乡村的道路网络，因为多源 KNN 查询一般常应用于在城市内寻找最近邻。本实验将研究表 5-2 中的参数对实验结果的影响。表中各个参数的描述如下：要返回的查询对象个数 k：k 的大小表明了用户所需的查询对象个数，k 值的幅动范围为 5-25。查询对象的稀疏度 s：s 的大小表明了路网中所有结点除以查询对象的个数。例如，s 的默认值 1000 表示每 1000 个路网结点就有 1 个查询对象。查询点的个数 m：m 的大小表明了对于一个多源 KNN 查询，查询点集内的查询点的个数，m 的幅动范围设为 10-50。符合论文之前描述的仓库与顾客的情境。
.....
结 论
随着空间路网数据库快速发展，基于位置的服务得到了广泛的应用。本文研究针对多源点的 K 近邻查询问题，取得了如下成果：
(1) 本文基于
