Continuous Pass-by Nearest Neighbors Query In Road Network

K-nearest neighbors (kNNs) query is used to find the k nearest neighbors of a query point. kNNs query has a wide range of applications in many scientific fields, such as knowledge discovery, data mining, pattern recognition and classification applications. Continuous k-nearest neighbors (CkNN) query is one of the most important research in the field of spatio-temporal databases. A CkNN query is defined to retrieve k-nearest neighbors (kNNs) of a query point continuously. CkNN query plays an important role in traffic forecast, traffic management, intelligent navigation, and has extensive application prospects in intelligent transportation systems, geographic information system, and military.In this paper, we do some works in these fileds, the main results are summarized as follows:Firstly, a CkNN query algorithm that query objects move with uncertain velocity is proposed for the situation that the speed of query objects and interest objects is limited. To improve efficiency, an effective method is also introduced to compute the candidate, reducing the CPU cost.Secondly, known the user's starting position and goal position, in order to get k interest objects (e.g. gas stations, etc.) passed by from the current position to the goal position, two methods of k pass-by nearest neighbors (kPBNN) query are proposed, which find kPBNN incrementally with the bidirectional search of A* and Dijkstra.Thirdly, as the user may move freely and kPBNN may change with the user's movement, on the base of kPBNN, we put forward a method of continuous kPBNN query.Finally, when the user does not care whether it is the shortest path and wants to take a route it likes, in order to give the user m optimal paths, another two schemas of m main roads (mMR) query and continuous mMR query are proposed on the basis of kPBNN query methods.Extensive experiments have proved the accuracy and effectiveness of all algorithms we proposed.