? Reverse Furthest Neighbors Query in Road Networks
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | FAQ
 
Indexed by   SCIE, EI ...
Bimonthly    Since 1986
Journal of Computer Science and Technology 2017, Vol. 32 Issue (1) :155-167    DOI: 10.1007/s11390-017-1711-5
Regular Paper Current Issue | Archive | Adv Search << Previous Articles | Next Articles >>
Reverse Furthest Neighbors Query in Road Networks
Xiao-Jun Xu1,2(徐晓军), Jin-Song Bao3,*(鲍劲松), Bin Yao4,5,*(姚斌), Member, CCF, ACM, IEEE, Jing-Yu Zhou4,5(周憬宇), Fei-Long Tang4,5(唐飞龙), Member, CCF, ACM, IEEE, Min-Yi Guo4,5(过敏意), Senior Member, IEEE, Member, CCF, ACM, and Jian-Qiu Xu6(许建秋)
1 School of Software, Beijing Institute of Technology, Beijing 100081, China;
2 First Research Institute of Ministry of Public Security, Beijing 100048, China;
3 College of Mechanical Engineering, Donghua University, Shanghai 200051, China;
4 Shanghai Key Laboratory of Scalable Computing and Systems, Shanghai Jiao Tong University, Shanghai 200240, China;
5 Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China;
6 College of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China

Abstract
Reference
Related Articles
Download: [PDF 2131KB]     Export: BibTeX or EndNote (RIS)  
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 pP 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 qQ, a BRFNR query fetches a set of points pP 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.
Articles by authors
Xiao-Jun Xu
Jin-Song Bao
Bin Yao
Jing-Yu Zhou
Fei-Long Tang
Min-Yi Guo
Jian-Qiu Xu
Keywordsreverse furthest neighbor   road network   landmark   hierarchical partition     
Received 2016-02-26;
Fund:

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.

Corresponding Authors: Jin-Song Bao, Bin Yao     Email: bao@dhu.edu.cn;yaobin@cs.sjtu.edu.cn
About author: Xiao-Jun Xu is currently a Ph.D. candidate in the School of Software, Beijing Institute of Technology, Beijing, and the associate director of the Information Technology Security Evaluation Center of the Ministry of Public Security, Beijing. His major interests include network and information security, cloud computing and big data mining.
Cite this article:   
Xiao-Jun Xu, Jin-Song Bao, Bin Yao, Jing-Yu Zhou, Fei-Long Tang, Min-Yi Guo, Jian-Qiu Xu.Reverse Furthest Neighbors Query in Road Networks[J]  Journal of Computer Science and Technology, 2017,V32(1): 155-167
URL:  
http://jcst.ict.ac.cn:8080/jcst/EN/10.1007/s11390-017-1711-5
Copyright 2010 by Journal of Computer Science and Technology