Username   Password       Forgot your password?  Forgot your username? 


Parallel Optimization of KNN Query Strategy based on Road Network

Volume 14, Number 10, October 2018, pp. 2366-2373
DOI: 10.23940/ijpe.18.10.p12.23662373

Boqi Hua, Hailong Suna,b, Fangsong Lib, Chao Jiangb, and Weitao Zoua

aCollege of Information and Computer Engineer, Northeast Forestry University, Harbin, 150040, China
bComputing Center of Heilongjiang Province, Harbin, 150026, China

(Submitted on July 12, 2018; Revised on August 15, 2018; Accepted on September 10, 2018)


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.


References: 15

                1. 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
                2. 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
                3. 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
                4. 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
                5. 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
                6. 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
                7. 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
                8. 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
                9. 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
                10. 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
                11. 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
                12. 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
                13. 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
                14. 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
                15. T. B. Hoff, “A Framework for Generating Network-based Moving Objects,” GeoInformatica, Vol. 6, No. 2, pp. 153-180, 2002


                              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.