如何快速从n点集中选取点P的k近邻点？

你提到的两种思路都是基础且实用的方案，各自有适用场景：

• 全量计算+排序：计算所有点与目标点P的距离，排序后取前k个最小距离对应的点。实现简单直观，适合点集规模n较小的场景，但时间复杂度为O(n log n)，当n很大时性能会明显下降。
• 维护最大堆（k大小栈）：遍历每个点计算与P的距离，同时维护一个容量为k的最大堆——堆顶始终是当前已筛选出的k个点中距离P最远的点。如果新计算的距离比堆顶小，就替换堆顶并重新调整堆结构。时间复杂度为O(n log k)，当k远小于n时，这种方法比全量排序高效得多。

除此之外，还有这些更高效的方案，适合不同的场景：

• 空间索引结构（适合多次查询）
  • KD-Tree：将点集按维度递归划分为二叉树结构，查询时可以快速剪枝掉不可能包含近邻的分支，平均查询时间复杂度为O(log n)。但这种结构在高维数据（比如维度>10）下性能会严重退化，更适合2-3维的低维场景。
  • Ball Tree：基于球体划分空间，通过计算点到球心的距离来剪枝无效分支，比KD-Tree更适配高维数据，查询效率更稳定。
  • R-Tree：常用于空间数据库系统，擅长处理矩形范围查询，也能用于k近邻搜索，适合批量空间数据的存储与查询场景。
• 近似k近邻算法（适合海量高维数据）
  • 局部敏感哈希（LSH）：通过特殊的哈希函数，将相似的点映射到同一个哈希桶中，查询时只需在目标点对应的哈希桶内筛选候选点，时间复杂度接近O(n)，适合高维海量数据的快速近似查询。
  • 层次可导航小世界图（HNSW）：构建多层图结构，通过逐层筛选快速定位到近邻区域，在百万级以上高维数据的查询中，速度远超精确算法，很多向量检索库都基于这个实现。
• 分治法（适合分布式场景）
  将点集拆分为多个子集，并行在每个子集中找出k近邻候选点，再将所有候选点合并，最后在合并后的候选集中筛选出真正的k近邻。这种方法适合分布式计算环境，能利用多节点算力提升处理速度。

内容的提问来源于stack exchange，提问作者Bruno Peixoto