移动对象的连续最近邻查询算法

《移动对象的连续最近邻查询算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、移动对象的连续最近邻查询算法于忠诚王金慧郭景峰（燕山大学信息科学与工程学院，秦皇岛"HH""#）B8D4CI：J45KLC57;C%H%M&H%$6:D摘要介绍了一种索引结构——@(.树和静态环境中基本的最近邻查询算法，并提出了影响时间这一概念，将其运用到最近邻查询算法中，可以完成移动对象的连续最近邻查询。关键词移动对象@(.树连续最近邻查询文章编号&""!8N%%&8（!""#）%%8"&ON8"%文献标识码*中图分类号@(%&&$&%!"#$%#&"&’()*+)’$()%,-."+/&)+%)’0"+1"2%#,3.4

2、)5$’6&7-"#,5-)#,8*#,9%#-&%:&"9%#,0)#,（P:IIEKE:Q>5Q:3D4FC:5)6CE56ERB5KC5EE3C5K，S45T745U5CVE3TCFW，XC57;45K94:"HH""#）;.’$+*5$：*5C59EYC5KTF3;6F;3E8@(.F3EE（FCDE8Z434DEFE3CGE9.F3EE）45924TC65E43ETF5ECK72:3[;E3CETC5TF4FC6E5VC3:5DE5F43EC5F3:9;6E9C5F7CTZ4ZE3$@7E6:56EZF:Q“C5Q

3、I;E56EFCDE”CTKCVE5459CFCT;TE9C55E43ETF5ECK72:3[;E3CET4IK:3CF7DF:CDZIEDE5F6:5FC5;:;T5E43ETF5ECK72:3[;E3CETQ:3D:VC5K:2LE6FT$<)=>"+?’：D:VC5K:2LE6FT，@(.F3EE，6:5FC5;:;T5E43ETF5ECK72:3[;E3W&引言=>?0>)@值排序。当一个结点被访问时，被从堆中移走，它的孩随着卫星定位系统（例如：’()）和无线通讯技术的快速发子根据它们的=>?0>)@值被添加到堆中。

4、这一过程不断重复展，跟踪并记录移动对象的位置成为可能，移动对象的连续最直到找到最近邻。1<是一个较为优越的算法，因为这种方法从近邻查询算法也成为研究的重点和难点。例如：“依照*车当所有结点中选择一个要处理的结点，可以从全局进行控制，从前的方向和速度，查询在未来+分钟内距离其最近的汽车。”而只访问必要的结点。尽管连续查询占据着很重要的位置，然而有效处理这种查然而，上述两种算法都是基于.树的、适用于静态环境下询的研究是有限的。在文,&-中，作者致力于建模和查询语言的的最近邻查询算法。该文提出的算法采用@(.树这一索引结研究，没有

5、提出具体的存取和处理方法。文,!-采用取样的方法构对动态目标进行索引，可以有效地完成移动环境下的连续最处理.树中的最近邻查询。这种方法递增地计算预定位置的近邻查询。结果，采用前一个点的计算结果计算后点，可以避免重复运算。然而，这种取样方法有着不可避免的缺点：如果采样频率很低，!@(.树（@CDE(434DEFE3CGE9.8F3EE）那么得到的结果可能会不正确；如果采样频率过高，则会产生@(.树,H-是.树的扩展，它能够索引动态目标并回答未来很大的计算量。在任何情况下，都无法保证结果是精确的，因为查询。一个动态目标的表示如下

6、：（&）当前时刻绑定这个动态目甚至较高的采样频率也会丢失一些结果。文,%-讨论了另一种解标的最小边界矩形=1.；（!）一个速度矢量。图&表示了两个决这个问题的方法（移动查询点，用.树索引的静态目标），采移动对象#和$，以及包含他们的边界矩形，箭头表示每个边用/0模型，只适用于查找一个最近邻。然而，上述这些方法都的速度方向，数字对应于速度的值，坐标轴负方向的速度是负不能够处理动态目标。值。在静态环境中，有两种基本的最近邻查询算法：1*1（234567845982:;59）算法,#-和1<算法,+-。1*1算法通过深度优先遍历.

7、树查询最近邻。首先，从根结点开始，所有的结点根据它们距离查询点的=>?0>)@值排序（=>?0>)@是指查询点!和结点"的子树中所包含目标的距离的最小值），具有最小值的结点首先被访问。这一过程不断重复直到叶子层中第一个可能的最近邻被找到。然后在向上一层返回的过程中，这个算法只访问那些=>?0>)@值小于当前被找到的最近邻的距离值的结点。图&@(.树中结点的表示1<算法采用了一个堆（AB*(）保存到目前为止已经访问过的结点。开始时，这个堆只保存根结点的孩子，并根据一个非叶结点也存储了一个=1.和它的速度矢量，=1.作者简介：于

8、忠诚，男，副教授，主要从事数据库应用技术、移动对象数据库、智能交通系统的研究。王金慧，女，硕士。主要从事移动对象数据库的研究。郭景峰，男，博士，教授，主要从事数据库应用技术，移动对象数据库，粗糙集，智能交通系统等的研究。&ON!""#$%%计算机工程与应用中紧紧包含着当前时刻的所有实体。非