CAJ | 학술논문

反向K最近邻查询需要确定以给定查询对象作为其k个最近邻之一的所有对象。然而由于大量应用需要处理未知数据，人们迫切需要能够处理未知对象的新算法。这里的主要问题是，一个对象属于RKN N结果集的事件不再是一个确定性事件，而是一个以一定概率成立的随机变量。对基于概率论的未知数据集反向K最近邻（PRKNN）搜索问题展开研究，以足够大的概率返回以查询对象为其最近邻的未知对象。基于一种新的考虑了距离相关性的修剪机制，提出一种PRNN高效查询算法。此外，还给出了如何将该算法扩展至PRKNN （其中k＞1）查询处理。最后，将该算法与当前其他最新算法作比较，实验评估结果表明，该算法性能明显优于其他算法。
반향K최근린사순수요학정이급정사순대상작위기k개최근린지일적소유대상。연이유우대량응용수요처리미지수거，인문박절수요능구처리미지대상적신산법。저리적주요문제시，일개대상속우RKN N결과집적사건불재시일개학정성사건，이시일개이일정개솔성립적수궤변량。대기우개솔론적미지수거집반향K최근린（PRKNN）수색문제전개연구，이족구대적개솔반회이사순대상위기최근린적미지대상。기우일충신적고필료거리상관성적수전궤제，제출일충PRNN고효사순산법。차외，환급출료여하장해산법확전지PRKNN （기중k＞1）사순처리。최후，장해산법여당전기타최신산법작비교，실험평고결과표명，해산법성능명현우우기타산법。
A reverse K-nearest neighbor query retrieves all objects having a given query object as one of their k nearest neigh-bors.However,due to the immense number of applications dealing with uncertain data,novel solutions to cope with uncertain objects are required.The main challenge here is that the event that an object belongs to an RKNN result set is no longer a predicate,but a random variable that may be true with some probability.This paper studied the problem of probabilistic re-verse K-nearest neighbor (PRKNN)search in uncertain databases,which returned the uncertain objects having the query ob-ject as nearest neighbor with a sufficiently high probability.It proposed an algorithm for efficiently answering PRNN queries using new pruning mechanisms taking distance dependencies into account.Finally,it compared the algorithm to state-of the-art approaches recently proposed.Experimental evaluation shows that the approach is able to significantly outperform previous ap-proaches.