论文摘要
随着无线网络通讯和全球定位技术的发展,出现了很多相关的新应用,如基于位置的服务。空间数据库(SDB)中支持基于位置服务的一种重要的查询就是连续k近邻查询。给定相关的空间数据点集和一个移动查询点q,道路网络中的连续k近邻(CkNN)查询计算距离一个给定查询点q最近的k个数据点。大多数关于空间数据库的研究只考虑欧氏空间。因此,大多数基于位置的查询,如k近邻查询,利用物体之间的欧氏距离。然而,在某些应用中,物体的位置和运动被限制于网络中,例如道路、航空、铁路等。在这些情况下,距离的度量是网络距离。为了存储这些网络中的空间数据,空间网络数据库(SNDB)出现了。每种传统的空间查询类型(如最近邻查询、范围查询、连接查询等)在空间网络数据库中都有相似的应用。对移动应用来说,支持道路网络中移动对象连续查询的能力是至关重要的。论文研究的连续k近邻查询处理三种类型的对象:道路、移动对象和静态对象。其中移动对象(如车辆或人)在道路网络上运动,静态对象(如加油站或旅馆)位于道路网络上;移动对象为查询点,静态对象为数据点。论文主要做了以下研究工作:首先,改进了道路网络模型并将道路网络模型转换为与其对应的图。其次,在该图的基础上结合Dijkstra单源最短路径算法实现了初始k近邻查询计算,并在移动对象运动过程中持续更新数据库与查询结果,将新的查询结果发送到客户端,实现了连续k近邻查询。最后,用实验证明了算法的正确性与有效性。