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 RfnR (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.