《移动对象连续K近邻查询处理技术研究》由会员分享，可在线阅读，更多相关《移动对象连续K近邻查询处理技术研究（74页珍藏版）》请在金锄头文库上搜索。
1、国防科学技术大学硕士学位论文移动对象连续K近邻查询处理技术研究姓名：牛剑光申请学位级别：硕士专业：摄影测量与遥感指导教师：陈荦2010-11国防科学技术大学研究生院硕士学位论文 第 i 页 摘 要 位置服务是通过移动终端和无线网络的配合，确定出移动用户的实际地理位置，从而提供用户需要的与位置相关的信息服务。在移动环境中，支持位置服务的移动对象数据库负责管理配备 GPS 等定位设备的移动对象如汽车、舰船、飞机等位置信息，并提供相应的查询服务，其中连续 K 近邻查询是移动对象数据库提供的基础查询服务之一，具有重要的研究价值。 经过十几年的研究，移动对象数据库领域取得了丰硕的研究成果，相关理论的进步
2、不断推动着位置服务的应用。然而作为一个系统级的应用，其对并发查询支持不足，尤其针对特定移动环境，仍需展开进一步研究以提高对多用户并发查询的支持。 本文针对多用户并发的移动对象连续 K 近邻查询问题，通过对经典技术深入剖析，结合实际应用背景，分别提出高度动态环境下和分布式计算框架下连续 K近邻查询算法。本文主要工作和创新点体现在以下方面： （1）面向高度动态的移动环境，基于查询索引的思想提出连续 K 近邻查询处理算法，给出了查询索引构建方法和查询处理流程，并通过实验验证了算法在高度动态环境下的先进性。 （2）提出移动对象连续 K 近邻查询的分布式计算框架，利用实际应用环境中查询客户端具有复杂计算
3、能力的特点，通过分布式计算大大降低服务器计算负荷，提高了查询处理效率。通过实验证明了该算法较以往服务器集中式算法性能优越。 （3）在设计实现高速的移动对象生成器基础上，设计实现了移动对象查询处理系统。该系统不仅为本文提供了实验环境，并且为今后相关研究提供了结果展示、算法正确性验证和性能测试的平台，同时作为一个位置服务模拟系统，也为今后将相关工作推向实用奠定了基础。 关键词：移动对象 连续 K 近邻查询 并发 高度动态移动环境 分布式框架 国防科学技术大学研究生院硕士学位论文 第 ii 页 Abstract Location based service(LBS) provides users w
4、ith services related to their positions which can be obtained through mobile devices and wireless networks infrastructure.In dynamic environment,the moving objects database(MOD) manage the positions of moving objects equiped GPS such as vehicles,fleets and airplanes,and provide location-dependent qu
5、eries. Continuous K-Nearest Neighbor(CKNN) Query is a kind of basic query provided by moving objects database ,is worth to research. After more than ten years research, key technologies of MOD have been extensively studied and rich achievements have been got.The advancement of technologies bring mor
6、e applications. However, MOD as a systematical application lacks of the support to concurrent query processing,especially,for some special environment.There are urge requirements on studying more to support concurrent query processing. To evaluate multiple continuous k nearest neighbor queries,throu
7、gh in-depth study on classical technologies,combined application background, This dissertation propose two algorithms,one on highly dynamic moving environment and the other base on a novel distributed computing framework.The main work and innovations are detailed as follows: (1) In highly dynamic en
8、vironment,we propose an algorithm for processing Multiple Continuous K-Nearest Neighbor Queries based on query index, discuss the solution to construct the grid index and evaluate the queries,and experimental results verify the effectivity . (2) Since actual query clients could implement complex com
9、puting, we propose a novel distributed computing framework of CKNN Query,which shares the burthen of server,and promotes the efficiency to process queries.The experimental results verify that this algorithm performs better than the algorithms centralized in server. (3) Based on a high-speed moving o
10、bject generater, we design and implemente a experimental system that supports multi-queries.The experimental system not only provides experiment platform,but also provides a platform to display, validate algorithms and test the performance.And,as basic LBS,the system establishs a foundation for prom
11、oting practicality of related work. Key words：moving objects, CKNN , Concurrent, highly dynamic moving environment, distributed framework 国防科学技术大学研究生院硕士学位论文 第 IV 页 表 目 录 表 3.1 算法实验参数设置 1 . 30表 4.1 算法实验参数设置 2 . 42表 5.1 移动对象生成器性能指标对比 . 53国防科学技术大学研究生院硕士学位论文 第 V 页 图 目 录 图 2.1 移动对象位置服务系统架构 . 7图 2.2 SEA-CNN图例 . 8图 2.3 YPK-CNN图例 . 9图 2.4 搜索区域过大 . 9图 2.5 CPM图例 . 10图 2.6 连续查询通用计算框架 . 12图 2.7 自适应安全区域 . 13图 2.8 基于空间划分的延迟更新策略 . 14图 2.9 周期性查询处理方案 . 16图 3.1 基于查询的格网索引 . 19图 3.2 查询索引构建方法 . 21图 3.3 单元格象限的定义 . 22图 3.4 查询Q在单元格中位置分析 . 23图 3.5 单元格扩
