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 (RfnR) 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 (MrfnR) query. Another interesting version of RfnR query is the bichromatic reverse furthest neighbor (BrfnR) query. Given two sets of points P and Q, and a query point q ∈ Q, a BrfnR 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 MrfnR and BrfnR queries, which utilize landmarks and partitioning-based techniques. Experiments on real datasets confirm the efficiency and scalability of proposed algorithms.
['Xiao-Jun Xu', 'Jinsong Bao', 'Bin Yao', 'Jingyu Zhou', 'Feilong Tang', 'Minyi Guo', 'Jianqiu Xu']
Reverse Furthest Neighbors Query in Road Networks