空间数据库中方向最近邻查询技术研究
发布时间：2021-04-14 15:17
近几年,空间数据库查询技术在智能识别系统、地理信息系统等领域具有越来越主要的地位。在空间数据库中,近邻查询是重要查询类型之一,但现有的最近邻查询并不能满足现实需求,所以最近邻查询的研究方向已由理想情况过渡到复杂的障碍环境,由于现有的近邻研究并没有针对地理方向的解决方法,因此本文重点解决在空间数据库中基于欧式环境、障碍环境的方向最近邻查询方法。首先,针对已有的最近邻查询方法,无法直接进行某一指定地理方向空间的最近邻查询问题,提出了方向最近邻查询方法。研究时分别从查询点为静态、查询点做匀速运动的两个情况进行研究。在查询点为静态情况下,首先利用平面直角坐标系与东西南北方向相结合的方式,提出了相应的剪枝方法及算法;再根据Voronoi多边形的最小外接矩形的性质,进行具体的查询并给出算法。在查询点做匀速运动的情况下,首先利用平面直角坐标系、东西南北方向与圆形相结合的方式,确定了查询范围;再根据运动轨迹与Voronoi图的位置关系,利用Voronoi图的性质进行具体的查询。进一步,由于现有的最近邻查询方法,无法在障碍环境下直接进行某一指定地理方向空间的最近邻查询问题,进而提出了障碍环境下的方向最近...
【文章来源】：哈尔滨理工大学黑龙江省
【文章页数】：55 页
【学位级别】：硕士
【部分图文】：
查询方向为东北方向的示意图
哈尔滨理工大学工学硕士学位论文-8-图2-2障碍环境下的Voronoi图Fig.2-2Voronoidiagraminobstaclespace定义2.4阻碍。在Voronoi图中，存在数据点pi，令点pi某个一阶临接Voronoi多边形所对应的数据点为pj。若在Voronoi图中存在Oi，使得Dpipj∩Oi≠，则称数据点pi与数据点pj被阻碍，记为pi—|pj；否则称称数据点pi与数据点pj未被阻碍，记为pi—pj。定义2.5障碍距离。若数据点pi与数据点pj被阻碍，则称数据点pi到数据点pj的最近距离为障碍距离，记为OD(pi,pj)。定义2.6阻碍阶数。若数据点pi与数据点pj被阻碍，且障碍距离OD(pi，pj)的长度仅与一个障碍物有关，则称数据点pi与数据点pj被一阶阻碍；若障碍距离OD(pi，pj)的长度与k(k≥2)个障碍物有关，则称数据点pi与数据点pj被k阶阻碍。2.3最近邻查询的基本方法传统的最近邻方法是基于R树的深度优先遍历方法。随后，国内外就最近邻查询提出了很多方法，比如广度优先算法、采样方法、对偶变换方法以及相对距离变换方法等。本节主要介绍比较典型的本文应用的最近邻查询的基本方法。2.3.1基于Voronoi图的查询方法Voronoi图是空间几何的重要分支之一。它以某种距离作为度量，对平面进行区域划分。Voronoi图的特性可以解决求最近点、最大空圆、最小树、n个平面点的凸包等问题。
哈尔滨理工大学工学硕士学位论文-11-如图3-1所示，查询点q的所在的位置为运动的起点，运动的终点为z，查询点q的运动方向为东北方向。当查询点q在起点时，采用传统的最近邻查询时，根据欧氏距离得出的最近邻应为数据点p1，此时的运动距离为（Dqp1+Dp1z）；采用现有的方向最近邻进行查询时，可能得出的方向最近邻集为{p4，p5，p6，p7}。根据本章所提算法可以直接得出方向最近邻结果为数据点p2，结果仅有一个数据点，且此时的运动距离为（Dqp4+Dp4z），（Dqp4+Dp4z）＜（Dqp1+Dp1z）。当查询点q运动时，根据所在的位置不同，得出的方向最近邻不同，当查询点q移动到q"时，此时的方向最近邻结果为数据点p8；当查询点q移动到q""时，此时的方向最近邻结果为数据点p3；当查询点q移动到q"""时，此时的方向最近邻结果为数据点p7。图3-1查询方向为东北方向的示意图Fig.3-1Whenthequerydirectionisnortheast3.2静态查询点下的方向最近邻查询在查询点为静态时的方向最近邻查询过程中，由于查询某一指定方向上的最近邻，其余方向上的数据集点是不需要考虑的，所以，本节提出的静态查询点下的方向最近邻查询包括两个步骤，即数据预处理过程和方向最近邻查询过程。数据预处理过程通过建立平面直角坐标系对数据集点的坐标进行正负判断和比较，进而得出所需方向的邻近点集，这样可以减少后续过程中计算量，缩短计算时间，并给出了剪枝算法。在方向最近邻查询过程中，通过构造Voronoi图和Voronoi多边形的最小外接矩形，利用Voronoi图的性质，给出算法得到准确的查询结果。
【参考文献】：
期刊论文
[1]障碍空间中不确定对象的组k最近邻查询方法[J]. 万静,唐贝贝,孙健,何云斌,李松. 哈尔滨理工大学学报. 2019(03)
[2]面向时间依赖路网的连续k近邻查询[J]. 李佳佳,李雨现,夏秀峰,王波涛,刘向宇. 计算机科学与探索. 2019(05)
[3]障碍环境中线段组最近邻查询方法研究[J]. 郭莹莹,张丽平,李松. 计算机科学. 2018(06)
[4]障碍环境下线段反k最近区域查询方法研究[J]. 张丽平,任玲玲,郝晓红,李松. 计算机科学与探索. 2018(10)
[5]路网环境下的最近邻查询技术[J]. 鲍金玲,王斌,杨晓春,朱怀杰. 软件学报. 2018(03)
[6]空间数据库中基于Voronoi图的线段组最近邻查询[J]. 郭莹莹,张丽平,李松. 小型微型计算机系统. 2017(10)
[7]障碍空间中基于Voronoi图的组反k最近邻查询研究[J]. 张丽平,刘蕾,郝晓红,李松,郝忠孝. 计算机研究与发展. 2017(04)
[8]一种基于密度网格索引的k-最近邻查询算法[J]. 章登义,李想. 电子学报. 2017(02)
[9]路网中线段反k最近邻查询研究[J]. 张丽平,郭莹莹,李松,李爽,樊瑞光. 计算机科学与探索. 2017(06)
[10]空间数据库中基于Voronoi图的组反k最近邻查询[J]. 张丽平,刘蕾,李松,于嘉希. 计算机科学与探索. 2016(10)
本文编号：3137547
【文章来源】：哈尔滨理工大学黑龙江省
【文章页数】：55 页
【学位级别】：硕士
【部分图文】：
查询方向为东北方向的示意图
哈尔滨理工大学工学硕士学位论文-8-图2-2障碍环境下的Voronoi图Fig.2-2Voronoidiagraminobstaclespace定义2.4阻碍。在Voronoi图中，存在数据点pi，令点pi某个一阶临接Voronoi多边形所对应的数据点为pj。若在Voronoi图中存在Oi，使得Dpipj∩Oi≠，则称数据点pi与数据点pj被阻碍，记为pi—|pj；否则称称数据点pi与数据点pj未被阻碍，记为pi—pj。定义2.5障碍距离。若数据点pi与数据点pj被阻碍，则称数据点pi到数据点pj的最近距离为障碍距离，记为OD(pi,pj)。定义2.6阻碍阶数。若数据点pi与数据点pj被阻碍，且障碍距离OD(pi，pj)的长度仅与一个障碍物有关，则称数据点pi与数据点pj被一阶阻碍；若障碍距离OD(pi，pj)的长度与k(k≥2)个障碍物有关，则称数据点pi与数据点pj被k阶阻碍。2.3最近邻查询的基本方法传统的最近邻方法是基于R树的深度优先遍历方法。随后，国内外就最近邻查询提出了很多方法，比如广度优先算法、采样方法、对偶变换方法以及相对距离变换方法等。本节主要介绍比较典型的本文应用的最近邻查询的基本方法。2.3.1基于Voronoi图的查询方法Voronoi图是空间几何的重要分支之一。它以某种距离作为度量，对平面进行区域划分。Voronoi图的特性可以解决求最近点、最大空圆、最小树、n个平面点的凸包等问题。
哈尔滨理工大学工学硕士学位论文-11-如图3-1所示，查询点q的所在的位置为运动的起点，运动的终点为z，查询点q的运动方向为东北方向。当查询点q在起点时，采用传统的最近邻查询时，根据欧氏距离得出的最近邻应为数据点p1，此时的运动距离为（Dqp1+Dp1z）；采用现有的方向最近邻进行查询时，可能得出的方向最近邻集为{p4，p5，p6，p7}。根据本章所提算法可以直接得出方向最近邻结果为数据点p2，结果仅有一个数据点，且此时的运动距离为（Dqp4+Dp4z），（Dqp4+Dp4z）＜（Dqp1+Dp1z）。当查询点q运动时，根据所在的位置不同，得出的方向最近邻不同，当查询点q移动到q"时，此时的方向最近邻结果为数据点p8；当查询点q移动到q""时，此时的方向最近邻结果为数据点p3；当查询点q移动到q"""时，此时的方向最近邻结果为数据点p7。图3-1查询方向为东北方向的示意图Fig.3-1Whenthequerydirectionisnortheast3.2静态查询点下的方向最近邻查询在查询点为静态时的方向最近邻查询过程中，由于查询某一指定方向上的最近邻，其余方向上的数据集点是不需要考虑的，所以，本节提出的静态查询点下的方向最近邻查询包括两个步骤，即数据预处理过程和方向最近邻查询过程。数据预处理过程通过建立平面直角坐标系对数据集点的坐标进行正负判断和比较，进而得出所需方向的邻近点集，这样可以减少后续过程中计算量，缩短计算时间，并给出了剪枝算法。在方向最近邻查询过程中，通过构造Voronoi图和Voronoi多边形的最小外接矩形，利用Voronoi图的性质，给出算法得到准确的查询结果。
【参考文献】：
期刊论文
[1]障碍空间中不确定对象的组k最近邻查询方法[J]. 万静,唐贝贝,孙健,何云斌,李松. 哈尔滨理工大学学报. 2019(03)
[2]面向时间依赖路网的连续k近邻查询[J]. 李佳佳,李雨现,夏秀峰,王波涛,刘向宇. 计算机科学与探索. 2019(05)
[3]障碍环境中线段组最近邻查询方法研究[J]. 郭莹莹,张丽平,李松. 计算机科学. 2018(06)
[4]障碍环境下线段反k最近区域查询方法研究[J]. 张丽平,任玲玲,郝晓红,李松. 计算机科学与探索. 2018(10)
[5]路网环境下的最近邻查询技术[J]. 鲍金玲,王斌,杨晓春,朱怀杰. 软件学报. 2018(03)
[6]空间数据库中基于Voronoi图的线段组最近邻查询[J]. 郭莹莹,张丽平,李松. 小型微型计算机系统. 2017(10)
[7]障碍空间中基于Voronoi图的组反k最近邻查询研究[J]. 张丽平,刘蕾,郝晓红,李松,郝忠孝. 计算机研究与发展. 2017(04)
[8]一种基于密度网格索引的k-最近邻查询算法[J]. 章登义,李想. 电子学报. 2017(02)
[9]路网中线段反k最近邻查询研究[J]. 张丽平,郭莹莹,李松,李爽,樊瑞光. 计算机科学与探索. 2017(06)
[10]空间数据库中基于Voronoi图的组反k最近邻查询[J]. 张丽平,刘蕾,李松,于嘉希. 计算机科学与探索. 2016(10)
本文编号：3137547
本文链接：https://www.wllwen.com/kejilunwen/shengwushengchang/3137547.html
最近更新
教材专著
