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.
1
$\begingroup$
$\endgroup$
11
$\begingroup$
$\endgroup$
The definition here 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$ – user331172 May 29 '17 at 4:21
-
$\begingroup$ @GeoMatt22 The reverse nearest neighbour relation is not a symmetric relation. $\endgroup$ – Dylan May 29 at 13:34
