反向最近邻查询研究综述

《反向最近邻查询研究综述》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、IsSN1009—3044⋯⋯‘一uJ⋯⋯⋯⋯⋯Compu~rKnowledgeandTechnology电脑知识与技术http：／／www．dnzs．net．cnVo1．7，No．28，October2011．Te1：+86—551-56909635690964反向最近邻查询研究综述张桂榕(西南大学计算机与信息科学学院，重庆400715)摘要：随着地理信息系统、数据挖掘和模式识别等领域研究的深入，最邻近查询及反最近邻查询近几年受到人们越来越多的关注。该文综述了有关反向最近邻查询的经典算法，并介绍了近两年来在此基础上的改进和新方法。关键词：最近邻查询；R—tree：Vorono

2、i图中图分类号：TP311文献标识码：A文章编号：1009—3044(2011)28—6913—04OverviewofReverseNearestNeighborQueryResearchZHANGGui——rong(CollegeofComputerandIn~rmadonScience，SouthwestUniversity，Chongqing400715，China)Abstract：NearestNeighborQueryandReverseNearestNeighborQueryhavereceivedmoreandmoreattentioninrecentyear

3、sbecauseofthedeepresearchODGIS，DataMimngandPat~mRecognition．SeveralclassicalgorithmsaboutRNNarecomprehensivelyelaborated，andsomeimprovementandnewmethodsachievedinrecenttwoyearsareintroduced．Keywords：nearestneighborquery；R—tree；Voronoicell最近邻查询(NearestNeighborQuery)是由Knuth在1973年提出来的，它是地理信息系统、

4、数据挖掘和模式识别等领域中重要的问题之一。在空间数据查询中，最近邻查询即寻找距离给定点或对象最近的点或对象，而对文本型数据来说，则是查找与给定对象意义最相近的对象。反最近邻查询(ReverseNearestNeighborQuery)是在最近邻查询的基础上提出来的，其含义就是在某个数据集中找出将给定查询对象作为最近邻的所有点的查询113。由于最近邻查询技术和反最近邻查询技术有着重大的理论和应用价值，因此它们一直是相关领域专家们研究的重点。到目前为止，已有多种最近邻查询和反最近邻查询方法被提出．下面将对近来广大学者对反向最近邻查询的研究做个简要综述。1基础知识1．1最近邻查询定义

5、1最近邻查询(NearestNei曲borQuery，简记为NN查询)：给定空问数据集P和～空问对象p，dist(p，pi)定义为P和P。之间的距离．最近邻查询是求P中的一个子集NN(p)。其中NN(p)满足表达式：NN(p)={piEPIVPJ∈P：dist(p，p0≤dist(p，p}它通常是用来找出距离一给定点最近的对象或对象集。定义2k最近邻查询(kNN查询)：给定空间数据集P和一空间对象P，dist(p，pj)定义为P和Pi之间的距离，k最近邻查询是求P中的一个子集kNN(p)，其中kNN(p)满足表达式翻：kNN(p)={pi∈PIVPJ∈P—kNN(p)：dist

6、(p，P，)~

7、点指针)的项组成，其中I是子结点指针指向的更低层结点项中所有矩形的MBR(最小外包矩形)。树中每个结点最多有M个条目，最少有m个(其中m≤M／2)，除非它是根。根结点至少有两个子结点，除非它是叶子『引。图1是一棵R一树的平面图和结构图。1．2．2R％一树R一树是R一树的一种变体，它对R一树的插入算法和分裂算法分别进行了一些改进，主要体现在以下两点：1)在R一树中，当插入一个节点时溢出，此时不会立即分裂此节点，而是先看此节点所处层次节点在本次插入中有没有做过重收稿日期：2011-07-20作者