电子学报 ›› 2017, Vol. 45 ›› Issue (2): 376-383.DOI: 10.3969/j.issn.0372-2112.2017.02.016

• 学术论文 • 上一篇    下一篇

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

章登义, 李想   

  1. 武汉大学计算机学院, 湖北武汉 430072
  • 收稿日期:2015-09-11 修回日期:2016-01-29 出版日期:2017-02-25 发布日期:2017-02-25
  • 通讯作者: 李想
  • 作者简介:章登义,男,1965年生于湖北省荆州市.武汉大学计算机学院教授,博士生导师.
  • 基金资助:

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

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

ZHANG Deng-yi, LI Xiang   

  1. School of Computer, Wuhan University, Wuhan, Hubei 430072, China
  • Received:2015-09-11 Revised:2016-01-29 Online:2017-02-25 Published:2017-02-25

摘要:

基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求,本文提出了一种基于密度网格索引的k-最近邻查询算法,该算法首先利用矩形的几何特点获取一系列候选搜索半径,随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤,尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明,实现了本文算法的密度网格索引在k-最近邻查询的查询效率上与ST2B-tree不相上下,而查询的I/O代价与其他索引结构相比有明显的优势.

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

Abstract:

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 ST2B-tree on the k-nearest neighbor query,but our algorithm has obvious advantages in the cost of I/O.

Key words: k-nearest neighbor query, moving objects, density grid, candidate search radii

中图分类号: