【作者】 孙冬璞；

【导师】 郝忠孝；

【作者基本信息】 哈尔滨理工大学 ， 计算机应用技术， 2010， 博士

【摘要】 时空数据库主要是用于存储和管理位置或形状随着时间的推移而发生变化的各类空间对象。随着对时空数据库需求的日益增加,对它进行深入的研究越来越受到人们的重视,最近邻(Nearest Neighbor, NN)查询作为时空数据库查询技术的重要组成部分自然也成为研究的重点和热点。最近邻查询的概念最先是在空间数据库中提出的,时空数据库在保持空间数据库最近邻查询含义不变的基础上,将所研究对象的运动状态从静止的扩充到运动的,因此使得这一查询过程更具有挑战性。尽管有许多科研人员致力于时空数据库最近邻查询的研究,目前也取得了很多卓越的成果,但随着研究的不断深入以及工业技术的持续发展,会发现对传统最近邻查询问题所提出的解决方法仍然存在不完善之处,对新型最近邻查询问题也存在许多有待研究之处,并且研究的内容还无法完全覆盖人们不断提出的复杂而多样的查询要求,因此对最近邻查询的研究仍然处在稳步发展之中,有待进一步的深入探索。鉴于此,本文主要对时空数据库的变体最近邻查询——多类型最近邻查询问题进行了研究,将其它最近邻查询问题与多类型最近邻查询问题相融合,从基础的静态多类型最近邻查询入手,逐步深化研究在存在障碍物和移动对象情况下的该类问题,使多类型最近邻查询问题更加具体化和实用化,完善时空数据库的查询处理技术,力求满足人们日益增长的、复杂而多样的查询要求。本文的主要贡献和创新可概括如下:(1)探讨了组最近邻查询问题,通过对不同个数的查询点的分布特征以及它们构成的几何图形的性质和特点的详细分析,结合组最近邻函数的特性,给出组最近邻所应满足的条件,利用Voronoi图的邻接性质,提出判断组最近邻的理论方法;提出基于Voronoi图的VTree索引,并在此基础上提出了基于VTree索引的组最近邻查询算法,从理论和实验两个方面分析和比较了所提出算法的性能,实验结果表明,在查询点不共线情况下,所提出算法的性能和稳定性好于在查询点共线情况下的性能和稳定性。(2)提出受限多类型最近邻查询问题,针对限制数据集的范围约束是任意简单多边形区域的情况,利用椭圆最小外接矩形的易求性、与椭圆本身覆盖区域的最近似性的特点以及用链表结构实现的剪枝策略,提出基于R树的受限多类型最近邻查询算法,并给出理论分析与实验分析的结果,分析结果表明,所提出的算法具有较好的性能。(3)对在障碍物环境中的多类型最近邻查询问题的特例问题——最优有序路径查询问题进行了研究,提出了k完全相异可视最优有序路径查询问题和障碍空间k全局相异最优有序路径查询问题,利用最近邻的思想分别对两类查询问题提出了近似查询算法,并利用实验对这些算法的性能进行了系统的分析,结果表明,所提出的算法在解决相应问题时具有较好的性能。(4)针对移动对象历史轨迹的连续最近邻查询问题,通过对轨迹之间的交点以及轨迹线段单调性等特征的分析给出理论支持,提出了在原始坐标下对一维移动对象历史轨迹连续最近邻查询的算法,实现了在不改变时空对象坐标系的情况下直接对一维移动对象历史轨迹连续最近邻的查询,给出实验分析和比较的结果,结果显示,所提出算法的性能优于已有算法的性能。(5)针对存在移动对象情况的最优有序路径查询问题,提出了移动对象的连续k最优有序路径查询问题,针对动态查询对象和静态数据对象的情况提出了处理该类查询的静态全局算法和动态局部算法,并对所提出算法的性能进行了实验分析,结果显示,所提出的算法能较好的解决该类查询问题。本文的研究成果是对时空数据库查询处理技术的有益补充和完善,为时空数据库的继续发展奠定了基础。更多还原

【Abstract】 Spatio-temporal database can be applied to storing and organizing every kind of spatial objects whose locations and forms are changing as time elapsed. The research on spatio-temporal database is paid more and more attention with the increasing requirements. As the important part of query processing techniques in spatio-temporal database, the nearest neighbor query has become a key and hot spot certainly. The concept of nearest neighbor query was first proposed in the theory of spatial database. Based on the unchanging meaning of nearest neighbor query, the object’s motion status is extended to contain moving objects besides static objects in spatio-temporal database. And it makes the query processing become more challenging. Although many scientific researchers are engaged in the nearest neighbor query research in spatio-temporal database and have made remarkable achievements so far, there are still some disadvantages in the existing methods to nearest neighbor query and many unresolved problems in the new nearest neighbor queries with the in-depth study of spatio-temporal database and continuous developments of industrial techniques. The complex and diverse query requirements that spring up unceasingly in real life cannot be covered completely by what the researchers studied on nearest neighbor queries in spatio-temporal database. As a result, the research on nearest neighbor queries in spatio-temporal database still develops steadily and thus a further explore will be required.In view of the above-mentioned facts, the variant of nearest neighbor query in spatio-temporal database, that is, the multi-type nearest neighbor query is studied in this dissertation. It combines the multi-type nearest neighbor query with other nearest neighbor queries. The static multi-type nearest neighbor query is first to be considered, and then the problems in the condition of existing obstacles and moving object are studied deeply. It makes the multi-type nearest neighbor query more concrete and practical. The motive is to perfect the techniques of query processing in spatio-temporal database, and meet the query requirements of users which become more and more various and complex. The innovative contributions in this dissertation are summarized as follows:Firstly, the group nearest neighbor query problem is discussed. The conditions which group nearest neighbor should be satisfied are proposed, which attained by analysing the distribution characteristic of query points, the attributes of geometric figures that they form and the qualities of group nearest neighbor function. The theories that evaluate the group nearest neighbor are put forward by combinational using the conditions and the adjacent property of Voronoi diagrams. The VTree index grounded on Voronoi diagrams is brought forward, and the algorithm is presented which deals with group nearest neighbor query based on VTree index. The performance of the proposed algorithm is analyzed through the theoretical and experimental aspects. Experimental results show that the performance and stability of the proposed algorithm in the condition of non-collinear query points are better than that in the condition of collinear query points.Secondly, the concept of constrained multi-type nearest neighbor query is put forward. In the case of the constrained datasets ranges which are constructed by arbitrary simple polygons, the query algorithm based on the R-tree is proposed. Some characteristics, such as the minimal circumscribed rectangle of an ellipse can be figured out easily and the area which it contains is no better than the area which is covered with the same ellipse, and the pruning strategies achieved by a list structure are used in this algorithm. The analysis results in theory and experiments are shown and indicate that the proposed algorithm has better performance.Thirdly, the specific problem of multi-type nearest neighbor query, named optimal sequenced route query problem, is studied in the condition of existing obstacles. The problems of k completely different visible optimal sequenced route query and k obstructed globally different optimal sequenced route query are proposed. The approximate query algorithms which deal with the two query problems respectively are put forward by using the idea of nearest neighbor. The performance of these proposed algorithms is verified systematically in the experiments, and the results show that these proposed algorithms have better performance.Fourthly, the continuous nearest neighbors query for historical trajectories of moving objects is studied. The theory is presented by analyzing the characteristics such as the intersections of trajectories and the monotonicity of trajectory segments, and in view of the theory, a method for query continuous nearest neighbors directly is proposed for historical trajectories of moving objects. The kind of method makes it possible not to change the coordinates of moving objects. The results of experimental analysis and comparison are brought forward and show that the method proposed has better performace than the existing methods.Finally, the problem of continuous k optimal sequenced route query for moving objects is put forward which aims at the optimal sequenced route query problem in the condition of existing moving object. The static-global algorithm and the dynamic-local one are proposed to answer such queries on the moving-query and static-objects case. The performance of the proposed algorithms is evaluated experimentally, and the results show that the proposed algorithms can resolve this query problem preferably.The production develops and perfects the query processing techniques in spatio-temporal database valuably, and lays the foundation of the further advances on spatio-temporal database.更多还原