Reverse Furthest Neighbors Query in Road Networks

详细信息    查看全文

• 作者：Xiao-Jun Xu ; Jin-Song Bao ; Bin Yao…
• 关键词：reverse furthest neighbor ; road network ; landmark ; hierarchical partition
• 刊名：Journal of Computer Science and Technology
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：32
• 期：1
• 页码：155-167
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Computer Science, general; Software Engineering; Theory of Computation; Data Structures, Cryptology and Information Theory; Artificial Intelligence (incl. Robotics); Information Systems Applications (
• 出版者：Springer US
• ISSN：1860-4749
• 卷排序：32

文摘

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.