软件工程硕士论文-移动对象轨迹的最近邻居查询研究.doc

优秀
密级:
硕士学位论文

论文题目移动对象轨迹的最近邻居查询研究
作者姓名×××
指导教师××× 教授
学科(专业) 软件工程
所在学院软件学院
提交日期 2007-05-15
A Dissertation Submitted to Zhejiang
University for the Degree of
Master of Engineering
TITLE: Nearest Neighbor Query Processing on Moving Object Trajectory
Author: ×××
Supervisor: Professor ×××
Subject: Software Engineering
College: College of Software Technology
Submitted Date: May 15, 2007
摘要
随着无线通讯和位置定位系统的发展,移动对象数据库(MOD)变得越来越重要,也对数据库研究提出了极大的挑战。基于时间和空间的查询算法成为一些基于位置的服务急需解决的问题。比如:交通控制,近邻信息访问和对野生动物迁徙特性的分析等。而其中一个重要的查询类型就是k最近邻居(kNN)查询。它主要用来查询离某一移动对象最近的k个轨迹。据我们所知,在已有的研究文献中,他们主要处理的是对于一系列连续移动点的将来或者当前位置的查询,这些查询或者基于静态的查询点或者基于连续移动的查询点。但是对于历史移动对象轨迹的最近邻居查询却很少。
基于此,在本文中,首先,我们提出了两种基于最佳优先(Best-First)策略的算法:BFPkNN和BFTkNN。分别用来处理静态查询点以及移动轨迹的k最近邻居(kNN)。并且为了减少内存消耗和CPU时间,本文给出了一些有效的剪枝策略。这些剪枝策略能够有效的避免访问那些不可能包含最终结果的节点,也能剔除掉那些不会成为最终结果的迹线段。其次,我们还提出了在历史移动对象轨迹上处理连续k最近邻居查询的两个算法:HCP-kNN和HCT-kNN。同时我们分析并给出了在连续kNN查询中常用的维护和更新k个最近邻居列表(kNearestLists)算法。再次,本文提出了在存储有历史移动对象轨迹的基于R树的索引结构上进行受限k最近邻居(CkNN)查询的概念,以及有效的处理方法。具体来说,为了有效处理CkNN我们提出了区域查询和kNN查询的依次查询方法以及在kNN查询中整合区域查询的方法。另外,我们还给出了两个算法,一个是截取迹线段得到时间域在某一范围内,空间区域包含在受限区域CR内的部分迹线段的算法,另外一个是截取节点获得时间在指定范围内,空间范围在CR内的部分记录的算法。
关键词移动对象轨迹,TB树,k最近邻居查询,受限k最近邻居查询
Abstract
With the integration of munications and positioning technologies, the concept of Moving Object Databases (MOD) has e increasingly important, and has posed a great challenge to the munity. Emerging location-dependent services call for new query processing algorithms and techniques to deal with both the spatial and temporal domains. Examples of these new services include traffic monitoring, nearby information accessing and migration patterns analyzing of wild animals. An important class of queries that is definitely useful for MOD processing is the so-called k nearest neighbor (k-NN) queries, where one is interested in finding the k closest trajectories to a predefined query object Q. To our knowledge, in the literature such queries primarily deal with either static or continuou