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 network...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.展开更多
基金This work was supported by the National Natural Science Foundation of China under Grant Nos. U1636210, 61472039, 61373156, 91438121, and 61672351, the National Basic Research 973 Program of China under Grant No. 2015CB352403, the National Key Research and Development Program of China under Grant Nos. 2016YFB0700502, 2016YFC0803000, and 2016YFB0502603, the Scientific Innovation Act of Science and Technology Commission of Shanghai Municipality under Grant No. 15JC1402400, and Microsoft Research Asia.
文摘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.
