摘要： 给定一个度量空间中的一组数据点集，k邻域问题在于对于某个数据点求出按照该空间的距离度量离数据点最近的k个数据样本。目前主要有2种方法，一种是基于立方体分割形成的三维立方体体素索引数组的体素栅格（CG（Cell Grid）方法，另一种方法是基于树索引结构的方法如kd-Tree等。论文主要研究经典CG方法及解决其内存消耗过多问题的两个改进方法：排序体素栅格（SCG）方法和投影体素栅格（PCG）方法。CG、SCG、PCG算法采用了改进的搜索方法，避免了传统CG算法[2-4]可能得到错误k邻域的问题。对三种算法的时空性能进行了分析比较，给出了相应的实验比较数据。
