移动对象全局K最接近邻居查询研究  

Algorithms for Global K Nearest Neighbor Query

作　　者：刘小峰[1] 陈传波[1] 刘云生[1] 

机构地区：[1]华中科技大学软件学院,湖北武汉430074

出　　处：《微电子学与计算机》2007年第9期4-7,共4页Microelectronics & Computer

基　　金：国家863计划项目(2006AA04Z211)

摘　　要：基于两个对象在一段时间内的范围距离度量,给出了一种新的时空查询形式-全局最接近邻居查询。该查询检索移动对象在一段时间内范围距离最小的运动对象。通过考察查询和连续最接近邻居之间关系,给出了一个基本查询处理算法。根据数据对象集的运动性不同,精化了运动和静止数据集下的全局距离的定义,并对R树结构索引的数据集给出了裁减、更新和访问启发式规则。采用分支界定技术和给出的启发式规则,设计了迭代的深度优先和基于堆的最好优先的查询处理算法。大量的实验表明,最好优先的查询处理算法具有突出的性能。This paper presented a new kind of query, global nearest neighbors query, which is based on a special distance, global distance, between two objects during given time interval. According to the relationship with continuous nearest neighbor query, a native algorithm is proposed. In terms of the mobility of data set, global distances at different situation are refined and some heuristics are presented for data set indexed by data structure of R tree family. Based on branch and bound technique and proposed pruning, updating and visiting heuristics, recursive depth-first and heapbased best-first query processing algorithms are developed for both cases. An extensive study based on experiments performed with synthetic data sets shows that the best-first algorithms outperform the depth-first algorithms.

关 键 词：移动对象数据库 最近邻居查询 分支界定算法 R树 

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