空间数据库中移动κ近邻线段查询技术的研究

《空间数据库中移动κ近邻线段查询技术的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级学位论文空间数据库中移动k近邻线段查询技术的研究作者姓名：指导教师：申请学位级别：学科专业名称：论文提交日期：学位授予日期：评阅人：张慧谷峪副教授东北大学信息科学与工程学院硕士学科类别：专业学位计算机技术2013年6月论文答辩日期：2013年6月2013年7月答辩委员会主席：申德荣教授张天成副教授赵明副教授东北大学2013年6月万方数据AThesisinComputerTechnologyStudyonMovingk-Nearest-·NeighborQueriesoverLi

2、neSegmentsinSpatialDatabasesByZhangHuiSupervisor：AssociateProfessorGuYuNortheasternUniversityJune2013万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：绝磐日期：二

3、句，；年6日>1日学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年√一年半口两年口学位论文作者签名：张仫导师签名：p中在劫任签字日期：加f-；干6}同州日签字日期：加f>耳()日引日．I．万方数据东北大学硕士学位论文摘要空间数据库中移动k近邻线段查

4、询技术的研究摘要随着个人电子设备的普及和通信技术的发展，基于位置的服务在日常生活中已经无处不在，如急救服务，道路导航和人员跟踪等。其中，空间数据库中的移动k近邻查询，由于巨大的应用需求，已经引起了学术界和工业界的广泛关注。目前关于移动k近邻查询的工作，均将查询对象抽象为点。但是现实世界中的查询对象，可能是河流、公路等复杂的线型事物，在这种情况下，传统方法将无法提供有效的服务。本文将复杂线型事物抽象为线段或者由一组线段组成的折线段，并从线段距离计算和线段安全区构建两个方面研究了空间数据库中移动k近邻的线

5、段查询技术。本文首先形式化定义了空间线段查询的基本概念，针对查询点与线段之间距离计算的复杂性，提出了线段划分区的概念来分类求解点与线段的距离。然后本文提出了移动k近邻线段查询安全区的构建算法LRkNN。LRkNN算法在RangeNN方法的基础上，仅需扫描部分数据对象建立局部安全区，在保证查询结果准确性和有效性的基础上，可以有效提高线段安全区的构建效率。此外为支持数据对象的动态变化，本文在安全区基础上提出了冲突域概念。如果变化的数据对象不包含于冲突域，则不需要重新计算查询结果。实验验证了本文所提出的LR

6、kNN算法在高效性和准确性上的优越性，相比基于抽样的方法，LRkNN在响应时间，I／0代价和通信代价方面至少提高一个数量级。为提高移动k近邻线段查询结果的可用性，通常需要对k个查询结果进行排序。因此，本文首先通过扩展IRU排序方法(即LIRU)，使其支持线段排序功能。然后基于V*-Diagram方法提出了LV木．Diagram技术及算法LMkNN，通过求解关于线段的安全区和LIRU结果的交集，构建线段的近似安全区，保证了查询结果的准确性和有序性。最后，提出折线段划分区的概念，在折线段划分区内，折线段问

7、题简化为单一线段问题。分别用Lv牛一Diagram技术构建每个折线段划分区内的线段安全区，来处理查询对象抽象为折线段的情况。LV+．Diagram技术同样可以支持数据对象的动态增删。如果动态变化的数据对象不在关于线段的安全区内，则查询结果的准确性和有序性不会受到影响。大量实验证明了该算法的有效性和高效性，相比基于抽样的方法，LMkNN在响应时间，I／0代价和通信代价方面至少提高一个数量级。总之，本文通过分析移动k近邻线段查询的典型特征和挑战，针对线段距离计算、安全区构建、查询结果的有序性和查询对象的动

8、态维护等方面的关键技术展开研究，提一II—万方数据东北大学硕士学位论文摘要高了整体查询处理效率。关键词：连续查询；移动k近邻查询；线段对象；安全区；动态数据库．．III．．万方数据东北大学硕士学位论文AbstractStudyonMovingk-Nearest-NeighborQueriesoverLineSegmentsinSpatialDatabasesAbstractWiththepopularityofpersonalelectronicdevi