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

doi:10.23940/ijpe.17.04.p17.501510

Abstract

Abstract:

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.

Submitted on February 13, 2017; Revised on May 5, 2017; Accepted on June 25, 2017
References: 15

Jia Liu, Wei Chen, Lin Zhao, Junfeng Zhou, and Ziyang Chen. kNN Research based on Multi-Source Query Points on Road Networks [J]. Int J Performability Eng, 2017, 13(4): 501-510.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

References 0

	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
	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
	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
	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
	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
	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
	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
	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
	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
	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)
	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
	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
	E. W. Dijkstra, “A note on two problems in connection with graphs,” Numerisce Mathematik, vol.1, no.1, pp.269–271,1959
	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
	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