Continuous K-Nearest Neighbor Queries for Uncertain Moving Objects
YU Yanwei1, QI Jianpeng1, SONG Peng1, ZHANG Yonggang2
1.School of Computer and Control Engineering, Yantai University, Yantai 264005 2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012
Abstract An urgent problem in location-based services is continuous K-nearest neighbor (KNN) queries for uncertain moving objects. An efficient algorithm for continuous K-nearest neighbor queries for uncertain moving objects is proposed. Firstly, two solutions, MaxMin and Rate, are proposed to predict the possible location range of the moving object in the time interval by utilizing the sampling points with velocities in the recent time window. A closed interval of minimum and maximum distances is employed to represent the distance between the query object and the moving object. Secondly, an optimized ranking method based on vague possibility decision is proposed to quickly find KNNs of the query object. Finally, experimental results on real and synthetic large-scale datasets demonstrate the effectiveness of the proposed algorithm.
Fund:Supported by National Natural Science Foundation of China (No.61572419,61403328,61302065), Natural Science Foundation of Shandong Province (No.ZR2014FQ016,ZR2013FM011), Key Program for Research and Development of Shandong Province (No.J2015GSF115009), Open Project of Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education of Jilin University (No.93K172014K13)
About author:: YU YanweiCorresponding author, born in 1986, Ph.D., lecturer. His research interests include data mining and distributed computing. QI Jianpeng, born in 1992, master student. His research interests include data mining. SONG Peng, born in 1983, Ph.D., lecturer. His research interests include machine learning and data mining. ZHANG Yonggang, born in 1974, Ph.D., associate profe-ssor. His research interests include data mining and knowledge engineering.
[1] 周傲英,杨 彬,金澈清,等.基于位置的服务:架构与进展.计算机学报, 2011, 34(7): 1155-1171. (ZHOU A Y, YANG B, JIN C Q, et al. Location-Based Services: Architecture and Progress. Chinese Journal of Computers, 2011, 34(7): 1155-1171.) [2] TAO Y F, PAPADIAS D, SHEN Q M. Continuous Nearest Neighbor Search // Proc of the 28th International Conference on Very Large Databases. New York, USA: VLDB Endowment, 2002: 287-298. [3] SONG Z X, ROUSSOPOULOS N. K-Nearest Neighbour Search for Moving Query Point // Proc of the International Symposium on Advances in Spatial and Temporal Databases. Berlin, Germany: Springer, 2001: 79-96. [4] KOLAHDOUZAN M R, SHAHABI C. Alternative Solutions for Continuous K Nearest Neighbor Queries in Spatial Network Databases. GeoInformatica, 2005, 9(4): 321-341. [5] MOURATIDIS K, YIU M L, PAPADIAS D, et al. Continuous Nearest Neighbor Monitoring in Road Networks // Proc of the 32nd Very Large Databases Conference. New York, USA: VLDB Endowment, 2006: 43-54. [6] 孙圣力,林 硕.一个高效的连续k近邻查询改进算法.计算机研究与发展, 2013, 50(Z): 80-89. (SUN S L, LIN S. An Improved Algorithm For Efficient Continuous KNN Queries. Journal of Computer Research and Development, 2013, 50(Z): 80-89.) [7] HUANG Y K, CHEN Z W, LEE C. Continuous K-Nearest Neighbor Query over Moving Objects in Road Networks // Proc of the Joint International Conferences on Advances in Data and Web Management. Berlin, Germany: Springer, 2009: 27-38. [8] 赵 亮,陈 荦,景 宁,等.道路网中的移动对象连续K近邻查询.计算机学报, 2010, 33(8): 1396-1404. (ZHAO L, CHEN L, JING N, et al. Continuous K Nearest Neighbor Queries of Moving Objects in Road Networks. Chinese Journal of Computers, 2010, 33(8): 1396-1404.) [9] 赵 亮,景 宁,陈 荦,等.面向多核多线程的移动对象连续K近邻查询.软件学报, 2011, 22(8): 1805-1815. (ZHAO L, JING N, CHEN L, et al. Continuous K Nearest Neighbor Queries over Moving Objects Based on Multi-core and Multi-threading. Journal of Software, 2011, 22(8): 1805-1815.) [10] YU X H, PU K Q, KOUDAS N. Monitoring k-Nearest Neighbor Queries over Moving Objects // Proc of the 21st International Conference on Data Engineering. Washington, USA: IEEE, 2005: 631-642. [11] XIONG X P, MOKBEL M F, AREF W G. SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-Temporal Databases // Proc of the 21st International Conference on Data Engineering. Washington, USA: IEEE, 2005: 643-654. [12] HUANG Y K, CHEN C C, LEE C. Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity. GeoInformatica, 2009, 13(1): 1-25. [13] LI G H, LI Y H, SHU L C, et al. CkNN Query Processing over Moving Objects with Uncertain Speeds in Road Networks // Proc of the 13th Asia-Pacific Web Conference on Web Technologies and Applications. Berlin, Germany: Springer, 2011: 65-76. [14] FAN P, LI G H, YUAN L, et al. Vague Continuous K-Nearest Neighbor Queries over Moving Objects with Uncertain Velocity in Road Networks. Information Systems, 2012, 37(1): 13-32. [15] SISTLA A P, WOLFSON O, XU B. Continuous Nearest-Neighbor Queries with Location Uncertainty. The VLDB Journal, 2015, 24(1): 25-50. [16] ARGE L, DE BERG M, HAVERKORT H J, et al. The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-tree.ACM Trans on Algorithms, 2008, 4(1). DOI: 10.1145/1328911.1328920. [17] YUAN J, ZHENG Y, XIE X, et al. T-Drive: Enhancing Driving Directions with Taxi Drivers' Intelligence. IEEE Trans on Knowledge and Data Engineering, 2013, 25(1): 220-232.
2016, Vol. 29 
