knn - 最近邻算法对非匹配快速

Question

我有一个在 100 维空间中有数百万个点的数据集。我需要快速检查查询点是否不在集合中任何点的一定距离内。

有没有快速的算法呢？

该算法可能有误报（比如查询靠近另一个点），但不能有误报（比如查询远离每个点，但不是）。

这里的难点是：

• 维数被诅咒了。这是一个广阔的空间，但一切都相对靠近。

• 大多数 KNN 算法专注于寻找最佳候选者，并拒绝比最佳候选者更远的所有点。在我的情况下，几乎每个查询都是“未命中”，因此最好的候选人始终无法拒绝甚至超过一半的分数。