不确定性对象的反向最近邻查询

《不确定性对象的反向最近邻查询》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第36卷第10期计算机工程2010年5月Vol.36No.10ComputerEngineeringMay2010·软件技术与数据库·文章编号：1000—3428(2010)10—0047—03文献标识码：A中图分类号：TP311.131不确定性对象的反向最近邻查询11,2王淼，郝忠孝(1.哈尔滨理工大学计算机科学与技术学院，哈尔滨150080；2.哈尔滨工业大学计算机科学与技术学院，哈尔滨150001)摘要：多数不确定性对象的反向近邻查询不能明确回答某个不确定性对象是否为查询对象的反向最近邻，针对该问题，提出概率反向最近邻查询的概念，设计不确定性对象的概率反向最近邻查

2、询的索引结构，给出一种基于该结构的不确定性对象的反向最近邻查询算法。关键词：反向最近邻查询；不确定性数据；概率反向最近邻查询ReverseNearest-neighborQueryonUncertainObjects11,2WANGMiao,HAOZhong-xiao(1.CollegeofComputerScienceandTechnology,HarbinUniversityofScienceandTechnology,Harbin150080;2.CollegeofComputerScienceandTechnology,HarbinInstituteofTech

3、nology,Harbin150001)【Abstract】Alotofreversenearest-neighborqueryonuncertainobjectscannotanswerwhethertheuncertainobjectisreversenearest-neighborofqueryobject.Aimingatthisproblem,thispaperproposesthenotionofprobabilisticreversenearestneighborquery,devisesaprobabilisticreversenearestneighb

4、orqueryindexandoffersareversenearestneighborqueryalgorithmonuncertainobjectsbasedonthisindex.【Keywords】reversenearest-neighborquery;uncertaindata;probabilisticreversenearestneighborquery基于不确定性的查询是当前研究的热点和难点。文精确对象的组织形式，用最小外包矩形MBR把数据空间中不献[1-5]对不确定性对象的范围、近邻和连接查询进行研究。确定性对象对应的MBR组织起来。例如有6个不确定

5、性对象基于不确定性对象的反向最近邻查询，在大多数情况下，不的数据集合P={a,b,c,d,e,f}，其中每个对象由包含20个可能像在确定性数据情况下能明确地回答某个不确定性对象Monte-Carlo采样点的3个点簇表示，在索引结构中的组织形是或者不是查询对象的反向最近邻。因此，本文对基于不确式如图1所示。定性对象的反向最近邻查询进行研究。不确定性maxdist(MBR(e),MBR(f))1基础知识对象a不确定性对象b本文的形式化定义如下：R1不确定义1(概率反向最近邻查询)数据空间P={o,o,…,o}R2定性12n对象d不确定性不确定性为n个不确定性对象的集合，对于

6、查询对象q的概率反向最对象cR3对象f点簇表示近邻查询的结果为形为(oi,pi)的元组的集合，其中，pi是oi同a略去为q的最近邻的非零概率。不确定性对象emindist(MBR(e),MBR(f))为了提高查询效率，利用文献[6]中的分簇算法，把每个C1(a)C3(a)不确定性对象o的离散表示集{o1,o2,…,os}分成k簇，主要思想就是把在空间上较为密集的点归为一簇。点簇表示点簇表示同a略去同a略去点簇表示[5]点簇表示同a略去定义2(对象的点簇表示)设{o1,o2,…,os}为不确定性对C2(a)同a略去象o的离散点集表示，则称{C1(o),C2(o),…,Ck

7、(o)}为不确定性对象o的点簇表示，其中，Ci(o)={oi,1,oi,2,…,oin,},图1点簇表示的不确定性对象集的组织形式i∪oij,={ooo,...,}且n1+n2+…+nk=s。下面给出该索引结构用到的几个距离函数，对于任意ikjn12s=1,2,,,=1,2,""i2个矩形R,R，距离的最小值记为mindist(R,R)，距离的12122索引结构设计最大值记为maxdist(R1,R2)，其中R1﹑R2可以为不确定性对[7]本文利用类似于RNN树的索引结构来组织如定义2所象的最小外包矩形，也可以为点簇的最小外包矩形。不确定