My questions is: What is the "real" difference between Reverse nearest neighbor(RNN) and Nearest neighbor(NN) queries? In my opinion, these two should return same result.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
The definition given by
states that
Given a multi-dimensional dataset $P$ and a point $q$, a reverse nearest neighbor (RNN) query retrieves all the points $p\in{P}$ that have $q$ as their nearest neighbor.
As a simple example, consider the 1D point set $P=[a,b,c]=[0,2,3]$. Then we have \begin{align} \mathrm{NN}(a) &= b \\ \mathrm{NN}(b) &= c \\ \mathrm{NN}(c) &= b \end{align} So \begin{align} \mathrm{RNN}(a) &= \emptyset \\ \mathrm{RNN}(b) &= \{a,c\} \\ \mathrm{RNN}(c) &= b \end{align} Does this help?
-
$\begingroup$ I got the logic, Exactly what i was looking for simple yet informative. Thank you! $\endgroup$ May 29, 2017 at 4:21
-
$\begingroup$ @GeoMatt22 The reverse nearest neighbour relation is not a symmetric relation. $\endgroup$– DylanMay 29, 2019 at 13:34
-
$\begingroup$ Could you include a full reference in case the link goes dead in the future? $\endgroup$ Jun 7, 2020 at 11:09
-