Scalable Continuous K-Nearest Neighbor Queries Method For Moving Objects

Nowadays,with the popularization of mobile devices,the IoT and smartphone APPs,massive-scale spatial-temporal data have been generated.Knowing the meanings hadden in these big data has far-reaching significance,especially in military,transportation,and human life.Therefore,this thesis focuses attention on continuous K-NN(K-Nearest Neighbors)query and proposes three algorithms.The main contributions are as follows:(1)We propose an efficient method for searching K-NNs of query object q with uncertain locations during a further time interval I.Firstly,we propose two solutions called MaxMin and Rate,which predict the possible location range of moving object during ? by utilizing the sampling points with velocities within the recent time window,and use a closed interval of minimum and maximum distances to represent the distance between the query object and moving object.Secondly,we propose an optimized ranking method based on vague possibility decision to quickly find K-NNs of the query object.(2)Based on Rate method for uncertain moving objects,we propose an efficient multi-core and multi-treading based framework for searching k-NNs of large scale queries with uncertain locations.Firstly,we propose a query reuse method for neighboring query objects in space.We use the velocities and locations of different query objects to judge whether employing query reuse,and certainly give the bound of reuse distance.Secondly,we propose a density grid based multi-treaded data partition method.Specifically,we partition the query objects into multiple threads by using high-density grids and adjacent grid expansion,which resolves the problem of load balance,and also group neighboring queries into the same thread to improve the reusability.Furthermore,we implement computation reuse for obtained predicted areas of moving objects by building shared memory over multi-core and multi-treading,which avoids a mass of redundant computation effectively.(3)Considering the computing bottleneck of a single computer for continuous K-NNs real-time query over massive data streams,we propose a scalable distributed continuous K-NNs query algorithm based on Storm(An open source distributed realtime computation system).First,we use router component,called Router Bolt,which integrates with a grid index to partition the current streaming data.To solve the problem of boundary points in the data partition,we propose an expanded grid structure to process the points in the boundary area.After that,we use K-NNs query component,named KNN Bolt,with PR-Tree index to implement an efficient distributed K-NNs real-time query algorithm to answer the K-NNs queres in parallel.Extensive experiments conducted on large-scale generated and real-world datasets demonstrate the effectiveness and efficiency of our proposed methods.