Parallel Optimization of KNN Query Strategy based on Road Network

doi:10.23940/ijpe.18.10.p12.23662373

Abstract

Abstract:

K-nearest neighbor (KNN) query is one of the most important query types in spatial databases and have been widely used in intelligent transportation, roadside assistance, and other fields. In order to improve the query efficiency, in this paper we adopted the MapReduce parallel computing framework of the Hadoop large data processing platform and completed the query of K neighbor moving objects by designing Map, Reduce, Combiner, and other functions. Before the start of the query, the road network was divided into pieces, and each fragment was calculated. The final K-nearest neighbor moving objects were obtained by aggregating the calculated results of each slice to realize the parallel optimization of the KNN algorithm based on road network. The experimental results showed that the performance of the parallel KNN algorithm based on MapReduce was better than that of the serial KNN query algorithm in a large-scale road network environment and a larger K value of query requests.

Submitted on July 12, 2018; Revised on August 15, 2018; Accepted on September 10, 2018
References: 15

Boqi Hu, Hailong Sun, Fangsong Li, Chao Jiang, and Weitao Zou. Parallel Optimization of KNN Query Strategy based on Road Network [J]. Int J Performability Eng, 2018, 14(10): 2366-2373.

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

References 0

	K. Mouratidis, M. L. You, D. Papadis, and N. Mamoulis, “Continuous Nearest Neighbor Monitoring in Road Networks,” in Proceedings of the 32nd International Conference on Very Large Data Bases, pp. 43-54, 2006
	H. J. Wang and R. Zimmermann, “Location based Query Processing on Moving Objects in Road Networks”, in Proceedings of the International Conference on Very Large Databases, pp. 432-443, 2007
	U. Demiryurek, K. Banaei, and C. Shahabi, “Efficient Continuous Nearest Neighbor Query in Spatial Networks Using Euclidean Restriction,” in Proceedings of the International Symposium on Spatial and Temporal Database, pp. 25-43, Aalborg, Denmark, 2009
	W. Liao, Q, Zhang, X. P. Wu, and Z. N. Zheng, “Research on Continuous k Nearest Neighbor Queries in Road Networks,” Journal of Chinese Computer Systems, Vol. 31, No. 4, pp. 666-671, 2010
	S. Aridhi, V. Benjamin, P. Lacomme, and L. B. Ren, “A Map Reduce-based Approach for Shortest Path Problem in Large-Scale Networks,” Engineering Applications of Artificial Intelligence, Vol. 41, No. 1, pp. 151-165, 2015
	T. Yokoyama, Y. Ishikawa, and Y. Suzuki, “All k-Nearest Neighbor Queries in Hadoop,” in Proceedings of Web-Age Information Management, Lecture Notes in Computer Science, pp. 346-351, 2012
	R. J. Barrientos, J. I. Gómez, C. Tenllado, M. P. Matias, and M. Marin, “KNN Query Processing in Metric Spaces Using GPUs,” in Proceedings of the 17th international European Conference on Parallel and Distributed Computing, pp. 380-392, 2011
	L. Zhao, N. Jing, L. Chen, W. Liao, and Z. N. Zheng, “Continuous K Nearest Neighbor Queries over Moving Objects based on Multi-Core and Multi-Threading,” Journal of Software, Vol. 22, No. 8, pp. 1805-1815, 2011
	A. Stupar, S. Michel, and R. Scheckel, “Rank Reduce-Processing K-nearest Neighbor Queries on Top of MapReduce,” in LSDS-IR, pp. 13-18, 2010
	C. Zhang, F. Li, and J. Jestes, “Efficient Parallel KNN Joins for Large Data in MapReduce,” in Proceedings of the 15th International Conference on Extending Database Technology, pp. 38-49, 2012
	Z. M. Ding, “An Index Structure for Frequently Update Network-Constrained Moving Object Trajectories,” Chinese Journal of Computers, Vol. 7, No. 35, pp. 1448-1461, 2012
	H. L. Sun and N. H. W, “CKNN Query based on RRN-Tree in Road Networks,” Computer Engineering, Vol. 40, No. 6, pp. 306-311, 2014
	P. Tomas, “Utilization of Graph Coarsening for Improving of Results of A Genetic Algorithm for Road Traffic Network Division,” in Proceedings of the 9th International Conference on Human System Interactions (HSI), pp. 28-34, 2016
	G. Karypis and V. Kumar, “METIS: A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices,” Technical Report, University of Minnesota, Department of Computer Science and Engineering, Army HPC Research Centre, Minneapolis, 1998
	T. B. Hoff, “A Framework for Generating Network-based Moving Objects,” GeoInformatica, Vol. 6, No. 2, pp. 153-180, 2002