针对k近邻算法的计算量过大和运行时间增加的问题，有以下几个方法可以使用：
KD-tree 算法：通过构建 KD-tree 数据结构，在查询时只需要搜索数据点周围的一部分区域，从而大大减少了计算距离的次数。
Ball-tree 算法：与 KD-tree 类似，但处理的数据更为高维，适用于处理较大的数据集。
Locality Sensitive Hashing：通过哈希技术将数据点分为不同的桶中，将相似的数据点划分到同一桶内，从而减少查询时需要计算距离的次数。
分治法：将数据集分为不同的子集进行计算，再进行合并。
除此之外，还有很多其他的优化方法，如增量式 k 近邻算法、最近邻搜索算法等等。推荐的文献包括：
An Efficient k-Nearest Neighbor Search Algorithm for High-Dimensional Space，作者为 T. Zhang 和 R. Ramakrishnan。
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality，作者为 M. Charikar。