空间网络数据库中反k最近邻查询算法

Algorithm for Reverse k-Nearest Neighbor Queries in Spatial Network Databases

在空间网络数据库中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,因此,基于欧氏空间的反最近邻查询算法不适用于空间网络数据库.本文对空间网络数据库中的反最近邻查询问题进行了研究.给出网络数据和兴趣点的索引结构及空间网络数据存储模型.给出查询空间修剪定理,并在此基础上,提出空间网络数据库中适用于单、双色反k最近邻查询的RkNN算法.证明了该算法的正确性.最后通过实验对算法进行了验证.

In spatial network databases, 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 spatial network databases. The problems about reverse nearest neighbor queries in spatial network databases are studied. Firstly, the index structure of network data and interest point and the storage model of spatial network data are presented. Secondly, the theorem to prune the search space is proposed too, based on it, the reverse k-nearest neighbor queries algorithm in spatial network databases is presented. The RkNN algorithm adapts not only monochromatic reverse k-nearest neighbor queries, but also bichromatic reverse k-nearest neighbor queries. Furthermore, the correctness of this algorithm is proved. At last, the validity of algorithm is showed by experimental result.