Research On Incremental Continuous K-Nearest Neighbor Queries

Continuous k nearest neighbor Query is an important query type in the spatio-temporal database, and it has got broad attention and application in traffic controller and location service. Different from tradition spatial kNN query that is reqired a calculated result one time, continuous k nearest neighbour inquiry requires that result must be renewed in time, to reflect the change of moving objects and queries. Therefore the query algorithm is more complicated, and it has become an international hot spot on a new study region. This paper analyzes and compares the internal and external researches of CKNN query method and studied large number of CKNN queries based on TPR-tree index.Firstly, SI-CNN query method makes partly use of query results which already have existed and does not take advantage of the increment thought, so that its efficiency is affected. To sovle this problem, this paper presents SS-CNN query method which caculates query result using the query of max similarity to fix the advance search region, so that it can make good use of query results. And examples of analysis and experimental validation results showed that it can deal with a large number of queries based on TPR tree effectively.Secondly, all the CKNN query methods need to search for the entire TPR tree, efficiency bringing about I/O visit price comparatively highly, affecting inquiry. To sovle this problem, this paper presents SR-CNN query method which calculates query result using dynamic increasing search region to avoid searching entire TPR-tree. And examples of analysis and experimental validation results showed that it is effective.Finally, we conducted experiments in a 104×104 the size of two -dimensional environment by using the spatial moving data points which generated by simulated environment. Verified the effectiveness and practicality of the two query methods presented in this paper by experimental results,and compared the efficiency of the two methods.