Reverse Furthest Neighbors Query in Road Networks

Given a road network G = (V,E), where V (E) denotes the set of vertices(edges) in G, a set of points of interest P and a query point q residing in G, the reverse furthest neighbors (Rfn_R) query in road networks fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in P ∪ {q}. This is the monochromatic Rfn_R (Mrfn_R) query. Another interesting version of Rfn_R query is the bichromatic reverse furthest neighbor (Brfn_R) query. Given two sets of points P and Q, and a query point q ∈ Q, a Brfn_R query fetches a set of points p ∈ P that take q as their furthest neighbor compared with all points in Q. This paper presents efficient algorithms for both Mrfn_R and Brfn_R queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.