一种对任意k的求解RkNN方法的研究-论文.pdf

《一种对任意k的求解RkNN方法的研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、。一⋯⋯一⋯一，，一⋯一，，一一⋯⋯⋯鼹UJlANCOMPU墨触一种对任意k的求解RkNN方法的研究黄志强(福建省特种设备检验研究院泉州分院福建泉州I362000)【摘要】：给定集合P和查询对象q，RNN返回的是P的子集P’，且P’中的任意对象。到q的距离都比O到P中的其他对象的距离小，即集合P’中的所有对象都以q为最近邻。本文了介绍一种求任意k的RkNN方法，并对该方法进行改进。【关键字】：空间数据库；最近邻；反最近邻1引言离按升序排序。并且从第一个值起，每到maxM个值反最近邻查询是空间数据库中常出现的一种查时，将这maxM个距离值存放在特定的某个Block中。询方法，是在最近邻

2、查询的基础上提出的一种新的查但如果当前Block为最后一块Block时，则只需将最询类型l1】。对于反最近邻查询的数学描述为：在空间数后剩余的未存到Block中的距离值存放到该Block据库中，对于给定的集合P和查询点q，如果P’P，中。对VO∈P’，P∈P，O≠p，dist(o，q)~

3、)与厶吲[，]进行比较，(i从1到N)，如果dist(q，p)≤(p3，pi)；dist(q，ps)／J、于Vi∈N，i≠5，dist(p5，pi)；而dist们，则P是以q为k-RNN的；否则，不是。(q，p1)>dist(p1，ps)，dist(q，p2)>dist(p2，ps)，dist(q，p4)>表1给出了图1集合P的任意两点的欧氏距离，dist(p4，ps)，dist(q，p6)>dist(p6，p4)，dist(q，pT)>dist(p7，以及q到集合P中所有点的欧氏距离，假设Block的p3)，dist(q，ps)>dist(p8，p1)。因此，我们得到RNN(q，P

4、)大小为5，则创建出来的Block如表2。那么当用户要=(p3，P5)查询的k-RNN为1一RNN时，则算法会选择Block为，的第1列的第i行与dist(q，pi)进行比较，i从1到-3t．’／ltN。那么如果Ib[i][1']<~dist(g，p)，则q是P的第1最近、邻点。因此，通过表1和表2，我们容易判定出P，和Pp8＼p5*P6都是与q为它们的第1最近邻点，而pl,p、P、P、P，和p4P都不以q作为它们的第1最近邻点。P2表1图1中各点的欧氏距离图1最近邻点示意图distp‘pp3ppp6pp反最近邻查询是一种比较成熟的技术，目前国内p2．82．13-22．24_33．4

5、1．O外在这方面也已经做了比较多的研究，但大部分都只p22．83．12．71．94．03_82．5是针对k较小的情况下的RkNN[2I洲，并不能很好的解p32．13．12．41．42．81．92．7决任意k的RkNN查询。本文提出的的RkNN算法就p43．22．72．41_21．92．03．6是对求解任意k的RkNN问题的一个研究。p52．21．91．41．22．61．72．42设计思想p64-34．O2．81．92．61．64．9(1)创建Block。p73．43．81．92．O1．71．63．9对于集合P中的所有点进行预处理，并将预处理ps1．02．52．73．62．44．93．

6、9后的信息存放在Block中。即：求出P中的每一点P(iq1．42．11-22-31．03．72．81．9从1到N)，以P中除P外的所有点的欧氏距离，将距2o14年第1期I福建电脑·147·瞩臻警敞瓣ljJlANC0}”双表2Block表集合P中的某一点P的位置序号。从而可以把存储空p1—1．02．12．22_83_2pl3．44-3间降为原来的，可节省一大部分的存储空间。P厂。÷1．92．52．72．83．1p2—3．84．0P31．41．92．12．42．7p3—2_83．1表3改进的P集合欧氏距离表distPIpmp4p5p6plosp4—’1．21．92．02．42．7p43

7、_23．6pl2．82．13．22-24-33．41．OP51_21．4I．71．92-2pr斗2．42．6p23．12．71．94．O3．82．5p6—I．6I．92．62．84．0pe『_+434．9p32．41．42．81．92．7P—1．61．71．92．O3．4p7—3．83．9p41．21．92．O3．6p52．61．72-4P1．02．42．52．73．6p3．94．9p61．64．9Block为，}Block为p73．9ps3算法设计q1．