路网环境下的多源最近邻查询方法研究

发布时间：2021-01-12 07:35

　　随着移动互联网技术的发展,大量应用的顺利部署和实施都不同程度依赖空间数据对象的查询。空间最近邻查询是空间对象涉及的主要查询种类之一,用于找到距离用户最近的目标对象。然而,目前的最近邻查询存在着查询源单一、查询结果分散无序、结果集过大且不能满足用户偏好等问题。针对上述问题,本文主要研究多源最近邻查询,用于返回满足空间约束条件和属性约束条件的目标对象,避免单源最近邻查询的不足。该查询不仅可以应用到选址分析、旅游规划、物流配送等日常生活服务的应用中,还可以应用到与位置有关的空间实体对象的查询、分析中。首先,针对现有最近邻查询的查询源单一的问题,利用空间距离约束为查询主要条件,研究由多个查询点组成查询源的最近邻查询方法。该研究基于两种单源基础算法（Dijkstra和IER）的结点扩展思想,提出基于局部优先策略和全局优先策略的多源最近邻查询算法,构建R树索引,并设计紧致上下界,缩小结点访问范围,提高算法性能。其次,针对现有最近邻查询结果分散无序、且存在现实目标对象位置集中（如商场、厂房、仓库等）的问题,研究空间距离和属性关键字共同约束下的多源最近邻查询,提出目标群的影响力计算方法和关键字查询算法... 

【文章来源】：燕山大学河北省

【文章页数】：122 页

【学位级别】：博士

【部分图文】：

路网局部示意图

图 2-2 R 树示例Fig. 2-2 Example of R tree B 树一样，R 树也是一颗平衡树，它用最小外接矩形(MBR)把空间距象集中于矩形框中，如果某个查询不能对应到某个矩形，则矩形内的是查询目标。R 树中的非叶子结点(根结点除外)所能拥有的子结点数目围。如果在 n 维空间下，M 表示子结点的最大个数，m 表示子结点的I 表示用来存储空间对象边界的坐标闭区间[a, b]，则 R 树有如下性质：1)所有非根结点包含有[m, M]个索引条目，通常 m = M 2。2)所有叶子结点都位于同一层。3)所有结点存储的记录条目中，I 是覆盖记录所代表目标对象的最小矩形图 2-2 b)所示，图中有 19 个区域，虚线框表示的区域为 R 树的内部7)，实线矩形框表示数据对象(R8~R19)。比如，树中根结点 R1包含 3 个R3、R4和 R5，另一个根结点 R2包含 2 个内部结点 R6和 R7，其中 R3包

花费更多的计算代价。鉴于此原因，在实际路网最近邻查询的过程中，产生了更多的 R 树的变体结构，对 R 树存在的问题做了改进，例如 VR 树[31]。2.2.2 四叉树索引结构四叉树通常也叫做四元树，是二叉树的高维变体结构，对于空间数据来说，四叉树在目标对象的最大覆盖范围内，迭代地将目标区域进行四块分割，直到每个被分割的最小区域中都包含目标对象，再根据目标划分区域的层次、个数，建立对应的索引，是一种非常有效的索引结构。四叉树的结构比较简单，对于目标对象分布比较均匀的网络来说，查询效率很高，是 GIS 和地图查询应用中的主要索引手段之一。常规四叉树结构如图 2-3 所示，平面示意图中有 8 个区域，每个区域可划分为更小的四个区域，如 b 区域中可以继续划分成 x，y，z 和 t 四个区域。在最近邻查询中，假设要查找的空间对象为 9，则正确的查询路径为：b→ →9。ba1

【参考文献】：
期刊论文
[1]一种GIS与集合覆盖法的消防区优化布局[J]. 刘莉,陈晨.  测绘科学. 2018(09)
[2]空间Skyline查询处理:应用、研究与挑战[J]. 余未,郑吉平,王海翔,王永阁,陈嘉良,江顺青.  计算机科学. 2017(02)
[3]基于聚类的路网上关键字查询[J]. 吴丹,杨卫东.  小型微型计算机系统. 2017(02)
[4]路网中基于预计算的跳跃式查询最近邻的算法[J]. 王恒.  天津理工大学学报. 2011(02)
[5]基于Voronoi图的最近邻查询的研究[J]. 王淼.  微计算机信息. 2008(33)
[6]空间网络数据库中最近邻查询的设计与实现[J]. 孙亚.  计算机科学. 2008(03)
[7]基于SR-树的空间对象最近邻查询[J]. 张奋,潘梅生,邹北骥.  计算机工程与应用. 2007(04)
[8]R树家族的演变和发展[J]. 张明波,陆锋,申排伟,程昌秀.  计算机学报. 2005(03)

硕士论文
[1]基于集合覆盖与智能优化算法的WCDMA网络基站位置优化[D]. 代超.华南理工大学 2013



本文编号：2972436