Study for cell grid methods finding k nearest neighbors
Hongwei Dong · Computer Engineering and Applications Journal · 2007
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.