一般来说，最近邻方法的一个缺点是在寻找最近邻和储存整个训练集时所需要的计算量。当有 $N$ 个观测样本和 $p$ 个自变量时，为每个待分类点寻找邻域点需要 $Np$ 次运算。已有一些可以降低计算量的一些寻找最近邻的快速算法（Friedman et al., 1975；Friedman et al., 1977）。Hastie and Simard (1998) 通过类比 K 均值聚类的方式降低了切空间距离的计算量。
降低储存的需求要更加困难，已被提出的方法有 编辑（editing） 和 压缩（condensing）。这个思路是在训练集中圈出一个可满足于最近邻预测的子集，然后舍弃掉剩余的训练样本。从直观上可知，这需要保留处于决策边界附近并且处在边界分类正确一边的样本点，而可以舍弃那些远离边界的点。
Devijver and Kittler (1982) 的 多次编辑（multi-edit） 算法将数据轮流地分成训练集和样本集，在训练集上计算最近邻分类规则，然后删除测试集中被误分类的点。其思路是在训练集上只保留同质性的簇。
Hart (1968) 的 压缩（condensing） 方法更进一步地只保留这些簇中处于外部边缘的重要的点。这个方法从一个样本集中随机选取的点开始，然后一个个地考虑其他的点，只有被当前选取的训练集上的最近邻误分类的点才会被加入到训练集中。
Dasarathy (1991) 和 Ripley (1996) 考察了这些方法。这些方法也可应用在除最近邻外的其他模型中。虽然这些方法有时会有帮助，不过我们在实际操作没有太多使用经验，同时在文献中也没有发现关于它们实际表现的系统性的比较研究。