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

ZHANG Deng-yi; LI Xiang

doi:10.3969/j.issn.0372-2112.2017.02.016

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-16

- A k-Nearest Neighbor Query Algorithm for Density Grid-Based Index
- Acta Electronica Sinica Vol. 45, Issue 2, Pages: 376-383(2017)
- 作者机构：
  
  武汉大学计算机学院,湖北,武汉,430072
- 作者简介：
- 基金信息：
- DOI：10.3969/j.issn.0372-2112.2017.02.016
  CLC： TP301
- Published Online：25 February 2017，
  
  Published：2017
- 稿件说明：
移动端阅览
ZHANG Deng-yi, LI Xiang. A k-Nearest Neighbor Query Algorithm for Density Grid-Based Index[J]. Acta Electronica Sinica, 2017, 45(2): 376-383.
DOI：

ZHANG Deng-yi, LI Xiang. A k-Nearest Neighbor Query Algorithm for Density Grid-Based Index[J]. Acta Electronica Sinica, 2017, 45(2): 376-383. DOI： 10.3969/j.issn.0372-2112.2017.02.016.

摘要

基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求，本文提出了一种基于密度网格索引的

-最近邻查询算法，该算法首先利用矩形的几何特点获取一系列候选搜索半径，随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤，尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明，实现了本文算法的密度网格索引在

-最近邻查询的查询效率上与ST

B-tree不相上下，而查询的I/O代价与其他索引结构相比有明显的优势.

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 ST

B-tree on the k-nearest neighbor query

but our algorithm h

as obvious advantages in the cost of I/O.

关键词

Keywords

references

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

⁰