Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (21): 52-56.
• 学术探讨 • Previous Articles Next Articles
DONG Hong-wei
Received:
Revised:
Online:
Published:
Contact:
董洪伟
通讯作者:
Abstract: Given a database or elements of a metric space,the k-nearest-neighbor problem consist in finding,for each element,its k nearest neighbors.Two approaches,one called CG(Cell Grid) method in this paper which based spatial cubic partitioning where the axis-aligned bounding box of the data points is partitioned by a cubical grid,and another based on tree structure such as kd tree are known for the problem.This paper concentrates on CG algorithm from which two improved algorithms called Sorted-Grid-Cell(SCG) and Projected-Grid-Cell(PCG) are presented.An improved k nearnest search process for CG,SCG and PCG is presented which avoids the wrong results occurred in the traditional CG algorithm used in paper [2-4].Comparisons for all the three algorithms are discussed and some empirical results are given.
Key words: k nearest neighbors, BSP tree, kd tree
摘要: 给定一个度量空间中的一组数据点集,k邻域问题在于对于某个数据点求出按照该空间的距离度量离数据点最近的k个数据样本。目前主要有2种方法,一种是基于立方体分割形成的三维立方体体素索引数组的体素栅格(CG(Cell Grid)方法,另一种方法是基于树索引结构的方法如kd-Tree等。论文主要研究经典CG方法及解决其内存消耗过多问题的两个改进方法:排序体素栅格(SCG)方法和投影体素栅格(PCG)方法。CG、SCG、PCG算法采用了改进的搜索方法,避免了传统CG算法[2-4]可能得到错误k邻域的问题。对三种算法的时空性能进行了分析比较,给出了相应的实验比较数据。
关键词: k最近邻域, BSP 树, kd树
DONG Hong-wei. Study for cell grid methods finding k nearest neighbors[J]. Computer Engineering and Applications, 2007, 43(21): 52-56.
董洪伟. 求k邻域的体素栅格算法研究[J]. 计算机工程与应用, 2007, 43(21): 52-56.
0 / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: http://cea.ceaj.org/EN/
http://cea.ceaj.org/EN/Y2007/V43/I21/52