Username   Password       Forgot your password?  Forgot your username? 


kNN Research based on Multi-Source Query Points on Road Networks

Volume 13, Number 4, July 2017 - Paper 17 - pp. 501-510
DOI: 10.23940/ijpe.17.04.p17.501510

Jia Liua,b, Wei Chena,b, Lin Zhaoa, Junfeng Zhoua, Ziyang Chena,c

aSchool of Information Science and Engineering, YanShan University, No.438, HebeiStreet West, Qinhuangdao and 066004, P.R.China
bDepartment of Information Engineering, Hebei University of Environmental Engineering, No.8, JingangRoad, Qinhuangdao and 066102, P.R.
cSchool of Information and Management, Shanghai Lixin University of Accounting and Finance, Shanghai and 201620, P.R.China

(Submitted on February 13, 2017; Revised on May 5, 2017; Accepted on June 25, 2017)


Given a query point set and an object point set, a multi-source query of k nearest neighbors (MQ-kNN) returns the query set for its k closest objects. However, most existing nearest neighbor query algorithms are based on a single-source query point (SQ-kNN), and the query point is often the user's location. However, in some cases, a query can be a point set. For example, a user wants to choose a house from the existing idle houses (query points) and hopes that its surrounding facilities (object points) are best. For this kind of application, we study the problem of MQ-kNN on road networks and try to solve MQ-kNN query problems. A basic algorithm based on Dijkstra algorithm is proposed as an original algorithm by calculating SQ-kNN repeatedly. Then, two improved algorithms are proposed by taking all query points as a whole and adopting the effective pruning strategy. Comprehensive experiments on five road network datasets clearly demonstrate the efficiency of this method.


References: 15

  1. C. S. Jensen, J. Kolárvr, T. B. Pedersen, and I. Timko, “Nearest neighbor queries in road networks,” in Proceedings of the 11th ACM international symposium on Advances in geographic information systems (GIS), pp.1–8, 2003
  2. D. Papadias, J. Zhang, N. Mamoulis, and Y. Tao, “Query processing in spatial network databases,” in Proceedings of International Conference on Very Large Data Bases (VLDB), pp.802–813, 2003
  3. M. Yiu, N. Mamoulis, and D. Papadias, “Aggregate nearest neighbor queries in road networks,” IEEE Transactions on Knowledge and Data Engineering archive (TKDE), vol. 17, no. 6, pp.820–833, 2005
  4. D. Papadias, Q. Shen, Y. Tao, and K. Mouratidis, “Group nearest neighbor queries,” in Proceedings of 20th International Conference on Data Engineering (ICDE), pp.301–312, 2004
  5. D. Yan, Z. Zhao, and W. Ng, “Efficient algorithms for finding optimal meeting point on road networks,” in Proceedings of the VLDB Endowment (PVLDB), vol. 4, no. 11, pp.968–979, 2011
  6. W. Sun, C. Chen, B. Zheng, C. Chen, L. Zhu, W. Liu, “Merged Aggregate Nearest Neighbor Query,” in Proceedings of the 22nd ACM Conference of Information and Knowledge Management (CIKM), pp.2243–2248, 2013
  7. J. B. Rocha-Junior and K. Nørvåg, “Top-k spatial keyword queries on road networks,” in Proceedings of International Conference on Extending Database Technology (EDBT). pp.168–179, 2012
  8. G. Li, J. Feng, and J. Xu, “Desks: Direction-aware spatial keyword search,” in Proceedings of the 2012 IEEE 28th International Conference on Data Engineering (ICDE), pp.474–485, 2012
  9. R. Zhong, J. Fan, G. Li, K.-L.Tan, and L. Zhou, “Location-aware instant search,” in Proceedings of the 21st ACM Conference of Information and Knowledge Management (CIKM), pp.385–394, 2012
  10. C. Deng, Y. Hu, T. Zhou, B. Wang, J. Suo, “A method of range nearest neighbor query of moving objects with uncertain velocity in road network,” Journal of Yanshan University, vol. 36, no. 6, pp.526–533, 2012 (in Chinese)
  11. G. Li, Y. Li, J. Li, L. Shu, F.Yang, “Continuous reverse k nearest neighbor monitoring on moving objects in road networks,” Information Systems, pp.860–883, 2010
  12. B. Lu, N. Liu, “Snapshot K neighbor query processing on moving objects in road networks,” Journal of Computer Applications, vol.31, no. 11, pp.3078–3083,2011
  13. E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerisce Mathematik, vol.1, no.1, pp.269–271,1959
  14. R. Zhong, G. Li, K. Tan, and L. Zhou, “G-Tree: An Efficient Index for KNN Search on Road Networks,” in Proceedings of the 22nd ACM international conference on Information & Knowledge Management(CIKM). pp.39–48, 2013
  15. K. Deng, X. Zhou, H. T. Shen, S. W. Sadiq, and X. Li, “Instance optimal query processing in spatial networks,” VLDB Journal, vol. 18, no. 3, pp.675–693, 2009


Click here to download the paper.

Please note : You will need Adobe Acrobat viewer to view the full articles.Get Free Adobe Reader

This site uses encryption for transmitting your passwords.