受限空间环境下的移动k近邻查询处理技术研究

《受限空间环境下的移动k近邻查询处理技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号UDC密级学位论文受限空间环境下的移动k近邻查询处理技术研究作者姓名：李传文指导教师：于戈教授东北大学信息科学与工程学院申请学位级别：博士学科类别：学科专业名称：计算机软件与理论论文提交日期：2011年7月论文答辩日期：学位授予日期：201i年。了月答辩委员会主席：评阅人：哼缮募丑欠跨豪Jk大学2011年7月工学2011年10月森凑毫ADissertationfortheDegreeofDoctorinComputerSoftwareandTheory,．StudyonMovingkNeareastNeighbor

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

3、O．f田学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年口一年口一年半口两年留学位论文作者签名：夕奎键文签字日期：伽叭f口．fo导师签名：寸戈签字日期：!eff．I口．∞．Il—东北大学博士学位论文摘要受限空间环境下的移动k近邻查询处理技术研究摘要随着移动定位技术以及空间索

4、引技术的不断发展，基于位置的服务也在越来越广泛的领域内得到了应用，例如在户外运动、旅游、物流运输甚至电子游戏等方面。基于位置服务的快速发展未来必然对人们的生产生活带来巨大的变革。如何响应移动中的用户对自己附近信息的查询，是基于位置服务领域的基础服务之一。如何高效、准确地处理这种查询，是决定基于位置服务应用前景的关键问题，得到了学术界和产业界的广泛关注。用户对于自身位置信息的获取可以通过GPS、移动网络定位、RFID标签等不同的方式获得。用户感兴趣的目标对象则以空间数据的形式存储在数据库中。针对不同的查询类型，可以通过事先

5、预处理的方式对数据库里的数据事先进行索引，以提高对应类型查询的处理速度。然而，查询类型多种多样、目标对象所处空间也各不相同，如何针对各种受限空间中不同种类的查询进行建模、预处理及实时处理，是目前基于位置服务领域中亟待解决的热点问题。移动k近邻查询作为基于位置服务中的一种基础查询，更有必要进行深入的研究。本文对各种受限空间中的特点和性质进行了归纳和总结，并对受限空间中移动k近邻的研究现状进行了分析和综述。我们针对多种不同类型的受限空间提出了相应的解决方案。在数据预处理、实时查询处理等方法提出了新的模型和解决方法，建立了一套

6、有特色的处理框架。这些技术可以有效地提高移动k近邻的实时处理效率和准确度，从而支持受限空问中的移动k近邻查询应用。具体的，本文对多种不同类型的受限空间中的移动k近邻查询进行了深入研究。这些空间包括障碍空问、存在不确定对象的障碍空间、权重空间等。同时，在对象点移动k近邻的研究基础上，将研究内容扩展到移动中路径近邻查询。本文的主要内容包括以下几个方面：(1)研究了障碍空问移动k近邻查询。对移动中进行k近邻查询的特点进行了分析，提出了一种有效地计算移动查询点的安全区域的方法，并将其扩展到障碍空间中。在对障碍空间的特点进行研究的

7、基础上，提出并证明了几个关于障碍空间中安全区域的实用性质。不同于之前的只能处理理想欧氏空间的查询，该方法东北大学博士学位论文摘要可以高效地处理障碍空间的移动查询问题。(2)研究了存在不确定对象的障碍空间移动k近邻查询。在存在障碍的空问中对不确定对象移动最近邻查询的处理方法进行了研究。建立了空间障碍物及不确定对象的理论数据模型，提出障碍空间中不确定对象最近邻查询问题。在运用了一种剪枝技术来提高性能的基础上，设计了一种高效的基于不确定空间距离的算法来进行查询处理。基于不确定对象分割区域设计出一种有效的安全区域生成方法。(3)

8、研究了权重空间移动k近邻查询。讨论权重空间中讨论了MkNN问题的独特性质。基于联接区域的概念，设计了一种高效的名为WeightedIndexingMap(WLM)的数据索引结构，以大量减少需要实时MkNN处理的时间。还设计了一种名为wNeighbors的基于WlM的WkNN查询算法。(4)研究了移动中对象路径近邻查询