? 路网上的反向最远邻查询
Journal of Computer Science and Technology
Quick Search in JCST
 Advanced Search 
      Home | PrePrint | SiteMap | Contact Us | Help
 
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 << Previous Articles | Next Articles >>
路网上的反向最远邻查询
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
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

摘要
参考文献
相关文章
Download: [PDF 2131KB]  
摘要 给定一个路网G=(V,E),其中V表示路网G中点的集合,E表示路网G中边的集合,一个含于V的兴趣点集合P和一个G中的查询点q,路网上的反向最远邻查询(RFNR)找出所有将点q作为其在集合P∪{q}中的最远邻居的点的集合。这又被称作路网上的单点反向最远邻查询(MRFNR)。同时还有另一类路网上的反向最远邻居查询,即路网上的多点反向最远邻查询(BRFNR)。给定一个路网G,一个含于V的兴趣点集合P,一个查询点集合Q以及任意一个q∈Q,路网上的多点反向最远邻查询找出所有将点q作为其在集合Q中的最远邻居的点的集合。本文利用地标和基于划分的技术,提出了分别适用于路网上的单点反向最远邻查询以及多点反向最远邻查询的高效率算法。基于实际数据的实验证实了本文所提出的算法的效率和可扩展性。
关键词反向最远邻   路网   地标   层次划分     
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.
Keywordsreverse furthest neighbor   road network   landmark   hierarchical partition     
Received 2016-02-26;
本文基金:

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.

通讯作者: 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.
引用本文:   
Xiao-Jun Xu, Jin-Song Bao, Bin Yao, Jing-Yu Zhou, Fei-Long Tang, Min-Yi Guo, Jian-Qiu Xu.路网上的反向最远邻查询[J]  Journal of Computer Science and Technology , 2017,V32(1): 155-167
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
链接本文:  
http://jcst.ict.ac.cn:8080/jcst/CN/10.1007/s11390-017-1711-5
Copyright 2010 by Journal of Computer Science and Technology