Research On Continuous Reverse Nearest Neighbor Queries In Road Network

Continuous reverse nearest neighbor (CRNN) query technology is an important topic in the field of spatial databases. A CRNN query continuous retrieves all the data objects that have the query data as their nearest neighbors. Due to the wide availability of positioning devices and the development of location-based services, the CRNN problem in road network has appeared in many practical systems such as decision support, traffic networks, resource distribution, and the technology of CRNN query has become a hot subject in the field of spatial databases.The technologies of RNN query are analyzed synthetically, based on these, the method for CRNN query in road network are studied from a completely new perspective.Firstly, in order to effectively express and store the road network, on the basis of integrated analysis and research of nearest neighbor query of moving objects based on road network method, road network modeling is proposed.It simulates the street intersection changing restriction and road section available condition with transition matrix and a flag bit, which simulated the simply limited road network. Then a storage schema with two layers of index structures is proposed to express and store the road network, the storage of network data and the sets of interest point are divided, and its components are discussed.Secondly, on the basis of storage schema with two layers of index structures, the pruning space theorem is presented and demonstrated, the CRkNN query algorithm based on network expansion is presented to solve the high cost problem of the conventional method for CRkNN query in road network, and also the correctness of this algorithm is proved and is analyzed through examples. Thirdly, the difficulty in R-tree index is that data is strictly organized according to Euclidean distance rather than network distance, the M-tree index structure is presented to organize road network objects. Due to the computation high cost of network distance, the road network embedding technology is proposed to map the network into an m dimensional vector space, and L_∞metric can be used to efficiently compute an approximation of network distance. Based on these, the CRkNN query algorithm based on M-tree and road network embedding technology is presented, and the time complexity of this algorithm is proposed.Finally, all the above mentioned algorithms are validated by experiments, and the experiment results are analyzed.