面向移动对象实时跟踪的查询优化算法的研究

《面向移动对象实时跟踪的查询优化算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、电子科技大学UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA硕士学位论文MASTERDISSERTATION论文题目面向移动对象实时跟踪的查询优化算法的研究学科专业计算机应用技术指导教师罗光春教授博导作者姓名赵禹学号200921060320万方数据分类号密级注1UDC学位论文面向移动对象实时跟踪的查询优化算法的研究（题名和副题名）赵禹（作者姓名）指导教师姓名罗光春教授博导电子科技大学成都（职务、职称、学位、单位名称及地址）申请学位级别硕士专业名称计算

2、机应用技术论文提交日期2012.03论文答辩日期2012.05学位授予单位和日期电子科技大学答辩委员会主席评阅人年月日注1注明《国际十进分类法UDC》的类号万方数据独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。签名：日期：年月日

3、关于论文使用授权的说明本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）签名：导师签名：日期：年月日万方数据摘要摘要近些年来无线通信网络高速发展，智能移动终端设备也迅速普及，提供基于位置的服务也逐渐成为这些移动设备的基本功能之一。通过移动终端查找最

4、近邻目标，即最近邻查询，逐渐成为位置服务中一项重要的应用，对该领域应用的研究具有很高的科研与实用价值。正是由于位置服务的大量普及，空间数据越来越具有海量性和复杂性，传统的针对静态环境的最近邻查询已经不能很好地适用于这种情况。因此，如何提高空间数据的最近邻查询技术，已经成为位置服务领域的研究焦点。针对动态环境下的最近邻查询，已经存在一些比较好的解决方法，比如YPKCNN算法，SEACNN算法和CPM算法，其中CPM算法是其中公认的最优秀的算法，但是其中大量的欧氏距离计算是阻止算法效率进一步提高的瓶

5、颈。另外，在实际应用中，大多数移动对象是移动轨迹无法预测的非确定对象，采用一般的最近邻查询算法势必会有一定的局限性，并且国内外在该领域的研究成果相对较少，因此本文提出了一种针对非确定对象的最近邻查询思路。本文基于CPM算法中概念分割的模型，通过分析总结当前最近邻查询研究的相关成果，采用树型结构对平面网格结构中的格室进行索引，用简单的数学运算代替复杂的乘方开放运算，破除了原始CPM算法中性能提升的瓶颈，同时使用数据流系统中的滑动窗口模型对算法进行进一步的改进，并最终提升了算法的执行效率。另外，在此基础

6、上，又提出了期望距离的概念，将最近邻查询算法扩展到非确定对象领域，并提出了空间数据中非确定对象的最近邻查询方法。本文的主要成果可做如下概括：(1)使用数据流技术中的滑动窗口模型对连续的最近邻查询进行优化，并提高了连续最近邻查询的效率；(2)用简单的数学运算代替复杂的乘方开方运算，减少最近邻查询算法中大量复杂的欧氏距离计算；(3)采用树形结构对格室进行索引，使算法能够尽早淘汰掉对查询结果不产生影响的格室，降低算法的处理代价；(4)提出了针对非确定对象的最近邻查询方法，使算法更加适用于实际场景；I万方数

7、据摘要(5)设计并实现了基于位置服务的最近邻查询原型系统，并对其中移动对象组件、位置服务器和显示终端的设计与实现方法进行详细介绍。整个原型系统主要用于验证本文中的算法，但也能够当作实际应用项目的原型系统使用。关键词：移动对象，最近邻，K近邻，概念分割，非确定对象II万方数据ABSTRACTABSTRACTInrecentyears,wirelesscommunicationnetworkhasbeenhighlydevelopedaswellastheintelligentmobiletermina

8、ls.Therefore,theLocationBasedServiceshasbecomeanimportantfunctionofthesemobiledevices.SearchingnearestneighborsbythesemobiledevicesisregardedasoneofthemostpopularapplicationsinLocationBasedServices;studiesonitarevaluableforscientificres