基本k近邻算法通过搜索数据集中相似度最高的k个样本来实现分类或者回归,其没有显式的学习过程,天然的具有简单、离线学习、适用于多分类等优点。由于该算法需要计算每个结点到其他所有结点的距离,所以也被称为全搜索算法(FSA,full search algorithm),因其获得最优k值需要O(N~2)的时间复杂度,所以计算代价比较高。目前主要有两种加速的算法,一种是结合树索引的精确近邻查找算法,这种算法虽然可以通过树索引结构减少距离的计算,但在高维数据中,其时间复杂度依然接近于FSA。另一种是近似近邻查找算法,它相较于精确近邻查找算法而言,虽然在查找近邻时略有偏差,但却在时间复杂度上有明显的优势,故而被广泛研究。在近似k近邻算法中,优先搜索k-means树算法是针对高维数据搜索查找的一种高效的近似近邻查找算法,其使用k-means聚类来构建树模型。由于k-means聚类本身的时间复杂度较低,且算法采用特定策略来对树进行近邻搜索,故而算法的效率很高。然而,高维数据中可能存在的属性噪声会直接影响该算法中k-means树的构建。针对这一问题,本文在基于优先搜索k-means树的基础上,通过Bagging(bootstrap aggregating)方法引入k-means森林,提出了优先搜索k-means森林算法。相较于原算法,该算法不仅时间开销更小,而且对于高维数据中的属性噪声也有一定的鲁棒性。同时,本文还在MPI的基础上,通过对该算法的并行化设计,使得其处理数据的效率得到进一步的提升。另外,为了尝试解决精确近邻算法依赖于树结构的问题,本文提出了一种球模型的近邻查找分类算法。该算法用k-means聚类产生的球来替代原本的数据集,而不再依赖于树结构,在提高分类效率的同时还降低了标签噪声对分类结果的干扰,从而能够在部分数据集上获得更好的效果。