RkNN搜索在空间数据库应用中的研究

摘要

随着Internet以及Web的迅速发展，使得网络上的信息量无比丰富，如何从海量的网络信息资源中及时、准确地找到所需的信息成为当今的一个研究热点。而实际上，一方面用户不得不忍受在海量的信息中搜索自己想要的信息的痛苦，而另一方面，信息发布者却希望对自己的信息感兴趣的用户能够迅速的接收到信息。所以，一个有效的解决方法是信息发布者只把信息发布给那些有可能对这些信息有兴趣的用户。 随着空间信息科学的发展，地理信息系统等方面的应用越来越广泛，作为空间科学的重要分支之一，地理信息系统在很多应用中都需要求给定对象的RkNN，它在智能导航、现代通讯、交通控制、气象预报等各个领域都有着广泛的需求。 在现实生活中，大部分数据都具有空间属性，例如，地址、客户统计分布数据或者资产分布数据等等。利用这些数据信息的空间属性进行数据分析，可以观察发展趋势，帮助您掌握机遇。总而言之，能够迅速有效地管理空间数据，并根据其空间属性进行分析，对于当今的企业来说，是势在必行的。尤其是在邮电通信、城市规划、公安交通等领域，空间属性比普通数据扮演着更为重要的角色[15]。 空间数据库自身也有很多特殊性，首先，空间数据对象有着复杂的数据结构，因为对于空间对象的描述除了有几何信息外，还有其它非空间的属性。因此，空间数据库通常都非常巨大：其次，空间数据对象常常是动态变化的，对于它们的插入、删除和更新交错进行，而且由于空间数据的次序难以有统一的标准，所以对其动态的管理难度很大。 RkNN搜索在空间数据库中有十分重要的应用，如GIs、生物基因研究等领域。然而现有的RkNN算法一般都是近似的解法或则仅仅适用于某种特定的情况，因此在一定程度上存在以下的不足和缺陷：仅适用于二维空间数据的求解；对k的值有限制；仅仅支持静态数据而不支持数据库的动态更新，尤其移动对象数据库；仅能得到近似不能得到精确的结果。 而相对于RkNN问题，kNN问题不仅研究得较早，而且对于它们的商业应用已经相当的广泛，所以相对于RkNN而言，kNN问题的研究已经相当成熟，而且存在较理想的算法。但遗憾的是，在一般情况下kNN与RkNN之间并不存在任何直接的转换关系，即r<'∈>NNS(q)并不意味着r<'∈>RNNS(q)。不过通过研究我们发现，在一定的条件的情况下，RNN(q) NN(q)和：RkNN(q) kNN(q)。即我们可以把：RkNN求解问题转化为kNN求解问题，通过相对来说成熟的kNN算法，最终达到求解RkNN的目的。基于此，本文提出了一个利用已有的kNN算法，在三维空间内能够支持数据更新且适合任意k值的RkNN算法。

目录

文摘

英文文摘

原创性声明和关于论文使用授权的说明

第1章绪论

1.1研究背景

1.2研究现状

1.3研究目标

1.4论文结构

第二章数学基础及相关技术

2.1地理信息系统(GIS)

2.1.1地理信息系统概述

2.1.2地理信息系统特点

2.2空间数据与空间数据库

2.2.1空间数据库

2.2.2空间对象

2.2.3空间数据特征

2.2.4空间数据模型

2.2.5空间数据库

2.3空间索引简介

2.3.1空间索引概论

2.3.2 R-Tree索引

2.3.3 R-Tree变形

2.3.4其它空间索引

2.4最近邻居搜索问题

2.4.1最近邻居(NN)

2.4.2最近邻居(NN)应用领域

2.4.3 kNN搜索

2.5 RNN

2.5.1 RNN的性质

2.5.2 RNN的性质证明

2.6 RkNN

2.7本章小结

第三章kNN搜索问题

3.1数学定义

3.2基于R-Tree的kNN搜索算法

3.2.1基于R-Tree的二维空间内的NN搜索算法

3.2.2基于R-Tree的二维空间内的kNN搜索算法

3.3一种新的空间索引Ra-Tree

3.3.1 Ra-Tree定义

3.3.2 Ra-Tree搜索算法

3.3.3 Ra-Tree的插入算法

3.3.4 Ra-Tree的删除算法

3.3.5 Ra-Tree的分裂算法

3.4基于Ra-Tree的kNN搜索算法

3.4.1基于Ra-Tree三维空间内的kNN搜索算法

3.4.2基于Ra-Tree二维空间内的kNN搜索算法

3.5本章小结

第四章基于kNN搜索算法的RkNN解决方案

4.1数学定义

4.2 RNN求解

4.2.1基于数据预处理的RNN求解

4.2.2基于RdNN-Tree的RNN求解

4.2.3利用RNN的性质求解

4.3二维空间内RkNN搜索到kNN搜索的转化

4.3.1二维空间内kNN与RkNN的关系

4.3.2二维空间内基于kNN的RkNN求解

4.3.3算法步骤

4.4三维空间kNN搜索到RkNN搜索的转化

4.4.1三维空间内kNN与RkNN的关系

4.4.2三维基于kNN的RkNN求解

4.4.3算法步骤

4.4.4算法性能分析

4.5本章小结

第五章总结与展望

5.1总结

5.2未来工作展望

参考文献

致谢

攻读学位期间发表的学术论文