一种道路网络中移动对象的K近邻多查询处理算法-中国人民大学.PDFVIP

第 卷 增刊 计 算 机 研 究 与 发 展 Vol. , Suppl. 2007 年 月 JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT . 2007 一种道路网络中移动对象的K近邻多查询处理算法 郝兴 王凌 孟小峰 ( 中国人民大学信息学院，北京 100872) ({haoxing, jingyiwang, xfmeng}@ruc.edu.cn) 摘要 在实际应用中，服务器时常会收到许多查询请求，因此如何高效地进行多查询处理，并且获得良好的吞吐量具有重要的 意义。本文研究了道路网络中连续的K 近邻多查询处理技术。在已知查询点位置和运动速度的情况下，将道路网络上的查询点 进行聚类，提出了基于聚类的K 近邻多查询处理算法，使同一聚类中的查询共享执行，从而大大提高多查询处理的效率。算法 还进一步利用扩展树存储查询结果，提高连续的 K 近邻多查询处理性能。理论分析和实验结果表明本文提出的算法是可行的， 高效的。 关键词 K 近邻查询；多查询处理；道路网络；聚类 中图法分类号 TP392 Multiple KNN Queries Processing for Moving Objects in Road Networks Xing Hao, Ling Wang , and Xiaofeng Meng (School of Information, Renmin University of China, Beijing 100872) Abstract In the real world applications ，severs often receive a lot of query requests, so how to process these queries efficiently and achieve better I/O efficiency is a challenging goal. This paper studies the multiple KNN queries processing for moving objects in road networks. Assume that the location and velocity of the query points in the road network are given, we cluster the query points and propose a Clu-MQN (Clustering based Multiple Queries in road Network) algorithm, which processes the queries in the same cluster synchronously, so the efficiency of query processing is greatly improved. Also the expansion tree is used to store the query results in order to improve the efficiency of processing multiple continuous k nearest neighbor queries. Theoretical and experimental analysis proved the feasibility and efficiency of the algorithm. Keywords k nearest neighbor query; multi queries processing; road network; cluster 1. 引言 在空间数据库研究中，K 近邻（KNN ）查询问题 查询[1,2]。二是基于空间网络（如道路网络）的KNN 受到广泛关注，这类查询被频繁地使用于地理信息系 查询[3,4]。本文研究的就是基于道路网络的 KNN 查 统（GIS ）等应用中。KNN 查询可以定义为：给定一