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

论文摘要

近些年来无线通信网络高速发展，智能移动终端设备也迅速普及，提供基于位置的服务也逐渐成为这些移动设备的基本功能之一。通过移动终端查找最近邻目标，即最近邻查询，逐渐成为位置服务中一项重要的应用，对该领域应用的研究具有很高的科研与实用价值。正是由于位置服务的大量普及，空间数据越来越具有海量性和复杂性，传统的针对静态环境的最近邻查询已经不能很好地适用于这种情况。因此，如何提高空间数据的最近邻查询技术，已经成为位置服务领域的研究焦点。针对动态环境下的最近邻查询，已经存在一些比较好的解决方法，比如YPK CNN算法， SEA CNN算法和CPM算法，其中CPM算法是其中公认的最优秀的算法，但是其中大量的欧氏距离计算是阻止算法效率进一步提高的瓶颈。另外，在实际应用中，大多数移动对象是移动轨迹无法预测的非确定对象，采用一般的最近邻查询算法势必会有一定的局限性，并且国内外在该领域的研究成果相对较少，因此本文提出了一种针对非确定对象的最近邻查询思路。本文基于CPM算法中概念分割的模型，通过分析总结当前最近邻查询研究的相关成果，采用树型结构对平面网格结构中的格室进行索引，用简单的数学运算代替复杂的乘方开放运算，破除了原始CPM算法中性能提升的瓶颈，同时使用数据流系统中的滑动窗口模型对算法进行进一步的改进，并最终提升了算法的执行效率。另外，在此基础上，又提出了期望距离的概念，将最近邻查询算法扩展到非确定对象领域，并提出了空间数据中非确定对象的最近邻查询方法。本文的主要成果可做如下概括：(1)使用数据流技术中的滑动窗口模型对连续的最近邻查询进行优化，并提高了连续最近邻查询的效率；(2)用简单的数学运算代替复杂的乘方开方运算，减少最近邻查询算法中大量复杂的欧氏距离计算；(3)采用树形结构对格室进行索引，使算法能够尽早淘汰掉对查询结果不产生影响的格室，降低算法的处理代价；(4)提出了针对非确定对象的最近邻查询方法，使算法更加适用于实际场景；(5)设计并实现了基于位置服务的最近邻查询原型系统，并对其中移动对象组件、位置服务器和显示终端的设计与实现方法进行详细介绍。整个原型系统主要用于验证本文中的算法，但也能够当作实际应用项目的原型系统使用。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文主要研究内容
• 1.4 本文组织结构
• 第二章 面向移动对象的最近邻查询技术
• 2.1 移动对象的特点
• 2.2 数据流技术
• 2.2.1 数据流查询处理机制
• 2.2.2 数据流查询处理计划
• 2.3 移动对象的连续 K 近邻查询技术
• 2.3.1 连续 K 近邻查询概念
• 2.3.2 经典的近邻查询算法
• 2.4 本章小结
• 第三章 基于概念分割模型的最近邻查询算法
• 3.1 最近邻查询算法
• 3.2 最近邻更新算法
• 3.3 基于数据流技术的连续 K 近邻查询算法
• 3.3.1 预备知识
• 3.3.2 连续 K 近邻查询算法
• 3.4 算法对比分析
• 3.5 本章小结
• 第四章 基于概念分割模型的最近邻查询改进算法
• 4.1 算法的改进思路
• 4.2 算法的改进方法
• 4.2.1 最近邻查询
• 4.2.2 最近邻更新
• 4.3 针对非确定对象的连续最近邻查询算法
• 4.3.1 问题描述与相关定义
• 4.3.2 针对非确定对象的最近邻查询方法
• 4.4 算法分析验证
• 4.4.1 改进的最近邻查询算法
• 4.4.2 针对非确定对象的最近邻查询算法
• 4.5 本章小结
• 第五章 移动对象实时跟踪原型系统的设计与实现
• 5.1 原型系统概述
• 5.1.1 总体架构
• 5.1.2 功能模块
• 5.2 原型系统各组件的设计与实现
• 5.2.1 移动对象生成器
• 5.2.2 位置服务器
• 5.2.3 显示终端
• 5.3 本章小结
• 第六章 总结与展望
• 6.1 主要研究成果
• 6.2 研究发展方向
• 致谢
• 参考文献