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

A k-Nearest Neighbor Query Algorithm for Density Grid-Based Index

作　　者：章登义[1] 李想[1] 

机构地区：[1]武汉大学计算机学院,湖北武汉430072

出　　处：《电子学报》2017年第2期376-383,共8页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60903035;No.41001296);国家863高技术研究发展计划(No.2013AA12A301)

摘　　要：基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求,本文提出了一种基于密度网格索引的k-最近邻查询算法,该算法首先利用矩形的几何特点获取一系列候选搜索半径,随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤,尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明,实现了本文算法的密度网格索引在k-最近邻查询的查询效率上与ST^2B-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 k-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 ST2 B-tree on the k-nearest neighbor query,but our algorithm has obvious advantages in the cost of I/O.

关 键 词：k-最近邻查询 移动对象 密度网格 候选搜索半径 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]