空间网络数据库中最近邻查询的设计与实现  

Design and Implementation of Nearst Neighbor Query in Spatial Network Database

作　　者：孙亚[1] 

机构地区：[1]浙江丽水广播电视大学理工教研室,浙江丽水323000

出　　处：《计算机科学》2008年第3期73-75,共3页Computer Science

摘　　要：随着无线通讯技术、位置定位技术以及数据库技术的发展,使得能为移动用户提供相关的位置服务。K近邻查询是位置服务的一个重要功能。本文主要研究了空间网络数据库中的K近邻查询。以提出的集成道路网络距离与欧式距离的道路网络框架为基础,提出了一种新的KNN查询算法,通过网络扩展方法计算最近邻(NN),避免了不必要的磁盘I/Os,减少了昂贵的最短路径计算,从而有效地提高了算法效率。实验结果说明,在目标点分布比较密集的情况下,算法显著优于其它的算法。With rapid advances in wireless communications, databases, and positioning technologies, it becomes possible to offer new e-services that provide mobile users with information about points of interesting. K nearest neighbor queries is essential for location-based position. In this paper we investigate k nearest neighbor searches in spatial net-work databases. We propose a road network architecture that integrates network and Euclidean information. Based on the architecture, we develop an efficient algorithm that calculates nearest neighbor. Experiments show that the algo-rithm outperforms other algorithms in high object density.

关 键 词：空间网络数据库 KNN查询 道路网络 

分 类 号：TP393.09[自动化与计算机技术—计算机应用技术] TP311.13[自动化与计算机技术—计算机科学与技术]