Reverse Nearest Neighbor Search Task

A reverse nearest neighbor search task is a similarity search task that requires finding all of the points with a query point [math]\displaystyle{ q }[/math] as their Nearest Neighbor.

Context:
- Input:
  - a Metric Space [math]\displaystyle{ M }[/math] (with Point Space [math]\displaystyle{ P }[/math] and Distance Function [math]\displaystyle{ d }[/math]).
  - a Query Point [math]\displaystyle{ q \in P }[/math].
  - a Positive Integer [math]\displaystyle{ k }[/math].
- output: all points in [math]\displaystyle{ P }[/math] for which [math]\displaystyle{ q }[/math] is their k-Nearest Neighbor.
- It can be solved by a Reverse Nearest Neighbor Search Algorithm.
Example(s):
- What are all the mailing addresses with fire station F as their nearest fire station?
- What are all of the airports for which airport A is their 2-nearest airport?
Counter-Example(s):
- a Nearest Neighbor Search Task.
- a Range Search Task.
- a Similarity Join Search Task.
See: Approximate Similarity Search Task.

References

(Zezula et al., 2007) ⇒ Pavel Zezula, Giuseppe Amato, and Vlastislav Dohnal. (2007). “Similarity Search - The Metric Space Approach." Tutorial at ACM SAC 2007.

(Zezula et al., 2006) ⇒ Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, and Michal Batko. (2006). “Similarity Search: The Metric Space Approach. Springer, Advances in Database Systems.