道路网络中移动对象的连续反k最近邻查询算法

在道路网络中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,基于欧氏空间的反k最近邻查询算法不适用于道路网络。为了解决道路网络中移动对象连续的反k最近邻查询问题,给出了道路网络的一种索引结构及一种利用扩展树处理查询的方法,在此基础上,提出了道路网络中适用与单、双色连续反k最近邻查询算法（CRkNNMA算法）,证明了该算法的正确性。

An algorithm for continuous reverse k-nearest neighbor queries of moving objects in road network

In road network, the position and movement of objects are constrained to a network, and the distance between two objects is network distance determined by the connectivity of the network, rather than traditional Euclidean distance. Therefore, reverse nearest neighbor queries algorithm basis on Euclidean space is not suitable to road network. In order to solve the continuous reverse k-nearest neighbor queries of moving objects in road networks, an index structure of road network and an method of using expansion tree processing queries are presented. Based on it, the continuous reverse k-nearest neighbor queries algorithm in road network is presented. The CRkNNMA algorithm adapts not only monochromatic continuous reverse k-nearest neighbor queries, but also bichromatic continuous reverse k-nearest neighbor queries. Furthermore, the correctness of this algorithm is proved.