一种连续最近邻查询的优化方法  

An optimal method for continuous nearest neighbor query

作　　者：周屹[1] 杨泽雪[1] 邢传军[1] 曲天伟[1] 

机构地区：[1]黑龙江工程学院计算机科学与技术学院,黑龙江哈尔滨150050

出　　处：《黑龙江工程学院学报》2013年第4期59-62,共4页Journal of Heilongjiang Institute of Technology

基　　金：黑龙江省教育厅科学技术研究项目(12521442)

摘　　要：连续最近邻查询是空间数据库中最重要的查询之一,在地理信息系统和位置定位服务等领域有重要应用。给定一个空间数据集P和查询线段q,连续最近邻查询返回结果<R,T>,其中T是一个间隔,R是这个间隔中所有点的最近邻。已有的连续最近邻查询算法无法实现I/O的优化,为此,提出一种优化的连续最近邻查询方法,该方法具有较高的I/O效率,不仅在减少磁盘访问数量方面进行优化,同时也提高CPU的性能。Continuous nearest neighbor query is one of the most important queries in spatial databases. It has important applications in the field of geographic information systems and location positioning services. Given a spatial data set of points P and a query segment q, the continuous nearest neighbor query result returns a set of 〈R, T〉 tuples, such that R is the NN of all points in the corresponding interval T. Existing continuous nearest neighbor query algorithms are not I/O optimal. An algorithm that has optimal 2/0 efficiency to compute the continuous nearest neighbor query is presented. The algorithm not only reduces the number of disk accesses, but also improves the CPU performance.

关 键 词：连续最近邻查询 空间数据库 地理信息系统 最近邻查询 

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