论文部分内容阅读
随着Internet以及Web的迅速发展,使得网络上的信息量无比丰富,如何从海量的网络信息资源中及时、准确地找到所需的信息成为当今的一个研究热点。而实际上,一方面用户不得不忍受在海量的信息中搜索自己想要的信息的痛苦,而另一方面,信息发布者却希望对自己的信息感兴趣的用户能够迅速的接收到信息。所以,一个有效的解决方法是信息发布者只把信息发布给那些有可能对这些信息有兴趣的用户。随着空间信息科学的发展,地理信息系统等方面的应用越来越广泛,作为空间科学的重要分支之一,地理信息系统在很多应用中都需要求给定对象的RkNN,它在智能导航、现代通讯、交通控制、气象预报等各个领域都有着广泛的需求。在现实生活中,大部分数据都具有空间属性,例如,地址、客户统计分布数据或者资产分布数据等等。利用这些数据信息的空间属性进行数据分析,可以观察发展趋势,帮助您掌握机遇。总而言之,能够迅速有效地管理空间数据,并根据其空间属性进行分析,对于当今的企业来说,是势在必行的。尤其是在邮电通信、城市规划、公安交通等领域,空间属性比普通数据扮演着更为重要的角色。空间数据库自身也有很多特殊性,首先,空间数据对象有着复杂的数据结构,因为对于空间对象的描述除了有几何信息外,还有其它非空间的属性。因此,空间数据库通常都非常巨大;其次,空间数据对象常常是动态变化的,对于它们的插入、删除和更新交错进行,而且由于空间数据的次序难以有统一的标准,所以对其动态的管理难度很大。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算法。