一种基于密度网格索引的κ-最近邻查询算法

摘要

基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求,本文提出了一种基于密度网格索引的κ-最近邻查询算法,该算法首先利用矩形的几何特点获取一系列候选搜索半径,随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤,尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明,实现了本文算法的密度网格索引在κ-最近邻查询的查询效率上与ST2 B-tree不相上下,而查询的I/O代价与其他索引结构相比有明显的优势.%The rapid development of location based services set higher demands on efficiency promotion and cost control of the services.In the paper,we propose a κ-nearest neighbor query algorithm based on density grid index.In processing of the algorithm,a series of candidate search radii is obtained by utilizing of the geometrical features of the rectangle.Then the appropriate candidate search radii are chosen to make distance filtering according to the density distribution of the moving object,it is useful to achieve reducing the unnecessary accessing to memory index units and disk index units.Our extensive experiments show that the efficiency of the density grid index with our algorithm is about equal to ST2B-tree on the κ-nearest neighbor query,but our algorithm has obvious advantages in the cost of I/O.