移动对象及其最近邻查询算法研究

作     者：翟丹润 

作者单位：河南大学 

学位级别：硕士

导师姓名：马骏

授予年度：2011年

学科分类：080904[工学-电磁场与微波技术] 0810[工学-信息与通信工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 080402[工学-测试计量技术及仪器] 0804[工学-仪器科学与技术] 081001[工学-通信与信息系统] 

主      题：最近邻查询 移动对象 空间数据查询 空间网络 Jensen模型 FNR树 

摘      要：移动计算、无线通信以及定位技术的快速发展使得对各种空间与时空对象的存储和管理成为了现实需求,也使得跟踪并记录移动对象的位置成为可能。大量的应用领域（如地理信息系统、智能导航、交通管制、天气预报、军事、移动电子商务等）均迫切需要有效地查询这些数据对象。因此空间数据查询的问题迅速成为了研究的热点,其中移动对象的最近邻查询作为空间数据查询中最重要的查询之一,也受到了社会各个领域的广泛关注。 移动对象的最近邻查询算法的查询效率是衡量其查询性能的重要指标之一,尽管已有许多的研究学者致力于这方面的研究,并取得了许多可喜的成果,然而,目前的研究大多集中在在如何提高单个查询请求的效率,但在实际应用时,服务器经常会同时收到大量的查询请求,用传统的最近邻查询算法在处理这种情况时效率就比较低。鉴于此,本文在对传统的移动对象最近邻查询算法的分析和研究的基础上,提出了一种基于对查询点聚类的最近邻查询算法。本文的主要贡献可归纳为: 1.对Jensen模型进行了扩充和完善,并给出了完整的路网和对象模型。为移动对象的最近邻查询算法的研究提供了符合实际的路网环境。 2.对基于路网的索引机制FNR树进行了改进,提出了FNR树,为移动对象的最近邻查询算法的研究提供了高效的索引支持,降低了检索移动对象的时间。 3.提出了基于聚类的移动对象最近邻查询算法CN。该算法针对移动对象快速变化的特点,对查询点进行聚类并计算出查询结果。算法在一定程度上解决了传统的基于路网的移动对象的最近邻查询算法在处理多个查询请求时效率低的问题。 4.利用移动对象生成器所产生的数据集,分别对CN算法与传统的算法和FNR树与FNR树进行了实验对比。实验结果表明,在一定条件下本文提出的CN算法的性能优于传统的算法,FNR树的检索效率优于FNR树的检索效率。