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

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

作　　者：朱彩云[1] 刘国华[1] 宋金玲[1,2] 李伟静[1] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北科技师范学院计算机系,河北秦皇岛066004

出　　处：《小型微型计算机系统》2009年第9期1781-1786,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60773100)资助;国家"十一五"科技支撑计划重点项目(2006BA05B02)资助;秦皇岛市科学技术研究与发展计划项目(2008-1-12)资助

摘　　要：在空间网络数据库中,对象的位置和运动被约束在网络中,对象之间的距离不是传统的欧氏距离,而是由网络连通性决定的网络距离,因此,基于欧氏空间的反最近邻查询算法不适用于空间网络数据库.本文对空间网络数据库中的反最近邻查询问题进行了研究.给出网络数据和兴趣点的索引结构及空间网络数据存储模型.给出查询空间修剪定理,并在此基础上,提出空间网络数据库中适用于单、双色反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.

关 键 词：空间网络数据库 最近邻 反最近邻 空间修剪 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]