Back to Search Start Over

Reverse Furthest Neighbors Query in Road Networks

Authors :
Feilong Tang
Minyi Guo
Jingyu Zhou
Jin-Song Bao
Xiao-Jun Xu
Jianqiu Xu
Bin Yao
Source :
Journal of Computer Science and Technology. 32:155-167
Publication Year :
2017
Publisher :
Springer Science and Business Media LLC, 2017.

Abstract

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.

Details

ISSN :
18604749 and 10009000
Volume :
32
Database :
OpenAIRE
Journal :
Journal of Computer Science and Technology
Accession number :
edsair.doi...........8ccc6c3b56b21582794614c7707bfa24
Full Text :
https://doi.org/10.1007/s11390-017-1711-5