【作者】 张慧；

【导师】 谷峪；

【作者基本信息】 东北大学 ， 计算机技术（专业学位）， 2013， 硕士

【摘要】 随着个人电子设备的普及和通信技术的发展,基于位置的服务在日常生活中已经无处不在,如急救服务,道路导航和人员跟踪等。其中,空间数据库中的移动k近邻查询,由于巨大的应用需求,已经引起了学术界和工业界的广泛关注。目前关于移动k近邻查询的工作,均将查询对象抽象为点。但是现实世界中的查询对象,可能是河流、公路等复杂的线型事物,在这种情况下,传统方法将无法提供有效的服务。本文将复杂线型事物抽象为线段或者由一组线段组成的折线段,并从线段距离计算和线段安全区构建两个方面研究了空间数据库中移动k近邻的线段查询技术。本文首先形式化定义了空间线段查询的基本概念,针对查询点与线段之间距离计算的复杂性,提出了线段划分区的概念来分类求解点与线段的距离。然后本文提出了移动k近邻线段查询安全区的构建算法LRkNN。LRkNN算法在RangeNN方法的基础上,仅需扫描部分数据对象建立局部安全区,在保证查询结果准确性和有效性的基础上,可以有效提高线段安全区的构建效率。此外为支持数据对象的动态变化,本文在安全区基础上提出了冲突域概念。如果变化的数据对象不包含于冲突域,则不需要重新计算查询结果。实验验证了本文所提出的LRkNN算法在高效性和准确性上的优越性,相比基于抽样的方法,LRkNN在响应时间,I/O代价和通信代价方面至少提高一个数量级。为提高移动k近邻线段查询结果的可用性,通常需要对k个查询结果进行排序。因此,本文首先通过扩展IRU排序方法(即LIRU),使其支持线段排序功能。然后基于V*-Diagram方法提出了LV*-Diagram技术及算法LMkNN,通过求解关于线段的安全区和LIRU结果的交集,构建线段的近似安全区,保证了查询结果的准确性和有序性。最后,提出折线段划分区的概念,在折线段划分区内,折线段问题简化为单一线段问题。分别用LV*-Diagram支术构建每个折线段划分区内的线段安全区,来处理查询对象抽象为折线段的情况。LV*-Diagram技术间样可以支持数据对象的动态增删。如果动态变化的数据对象不在关于线段的安全区内,则查询结果的准确性和有序性不会受到影响。大量实验证明了该算法的有效性和高效性,相比基于抽样的方法,LMkNN在响应时间,I/O代价和通信代价方面至少提高一个数量级。总之,本文通过分析移动k近邻线段查询的典型特征和挑战,针对线段距离计算、安全区构建、查询结果的有序性和查询对象的动态维护等方面的关键技术展开研究,提高了整体查询处理效率。更多还原

【Abstract】 With the popularity of personal electronic devices and the development of communication technology, location based services (LBS) have been ubiquitous in our daily life, such as emergency medical service, GPS navigation and people tracking. Among which, moving k nearest neighbor queries in spatial databases have attracted wide attention in academia and industry due to the huge demand of it. All the current works on moving k nearest neighbor queries model the query objects as points. Nevertheless, the query objects in real world could be complicated linear objects, such as rivers, highways, etc. In this case, the traditional method will not be able to provide effective services. In this article, the complex linear objects are modeled as line segments or polylines consisting of a set of line segments, and moving k nearest neighbor queries over line segments in spatial databases have been studied from aspects of line distance calculation and line safe region construction.Firstly, this article formally defines the basic concept of queries over line segments in spatial databases. Then aiming at the complexity of calculating distance between a point and a line segment, the concept of line-segment divided region has been proposed to separately calculate the distance between points and line segments. After that an algorithm of constructing the safe region of moving k nearest neighbor queries has been presented, which is named LRkNN. The LRkNN algorithm which is on the basis of RangeNN, can construct a local safe region of line segments by accessing only a part of data objects. LRkNN can effectively improve the efficiency of the construction of safe region of line segments on the premise of ensuring the accuracy and effectiveness of query results. In addition, in order to support the dynamic changes of data objects, the concept of impact region is proposed based on safe region. If the changing data objects are not contained in the impact region, the recalculation of query results is not needed. The superiority of LRkNN in efficiency and accuracy is verified by the experiments. Compared with the sampling based method, LRkNN increases at least one order of magnitude in response time, I/O costs and communication costs. To improve the usability of moving k nearest neighbor queries, a rank of query results is usually needed. Therefore a LIRU algorithm is presented by extending the IRU algorithm to support the sorting of line segment objects. Then, the LV*-Diagram based on V*-Diagram and the algorithm LMkNN are proposed to construct an approximate safe region by intersecting the region constructed by LIRU and safe region with regard to line segment, which can ensure the accuracy and rank of the query results. At last, it is put forword the concept of polyline divided region in which moving k nearest neighbor queries over polyline is simplified to queries over a single line segment. The moving k nearest neighbor queries over polyline are handled by constructing safe region of line segment using LV*-Diagram in each polyline divided region. LV*-Diagram can also support dynamical addition and deletion of data objects. If the changing data objects are not contained in the safe region with regard to line segment, the recalculation of query results does not needed. The superiority of LRkNN in efficiency and accuracy is verified by the experiments. Compared with the sampling based method, LRkNN increases at least one order of magnitude in response time, I/O costs and communication costs.In summary, by analyzing the typical feature and challenge of moving k nearest neighbor queries over line segment, this article conducts research on key technology of distance calculation between a point and a line segment, safe region construction, the orderliness of query result and the dynamic maintenance of query objects and improve the overall efficiency of query processing.更多还原