An Efficient Algorithm for Arbitrary Reverse Furthest Neighbor Queries

Given an object set

O

and a query object

q

, the reverse furthest neighbor (RFN) query retrieves the objects in

O

, whose furthest neighbor is

q

. In this paper, we consider the arbitrary RFN query that is without constraint of its location. The state-of-the-art method is not efficient for such kind of queries. Therefore, we address this problem by introducing our new findings on the filtering techniques. Firstly, we show the evidence that exhibits the inefficiency of the state-of-the-art method. We then figure out a non-trivial safe area to guarantee the efficiency for query processing, even meeting the ideal efficiency. We also design an efficient algorithm to answer the RFN query without any cost of filtering or refinement, when

q

is located in such safe area. Extensive experiments on both synthetic and real datasets are conducted to evaluate the effectiveness, efficiency and scalability of our algorithm. The results sufficiently indicate that our algorithm significantly outperforms the competitive ones in all the aspects.