computational-geometry - 在高暗空间中具有动态插入的 kNN

Question

我正在寻找一种方法来为高维点(通常 ~11-13 维)做快速最近邻(希望 O(log n))。我希望它在初始化结构后在插入过程中表现最佳。我想到了 KD 树，但是如果您不进行批量加载而是进行动态插入，那么 kd 树将不再平衡，而 afaik 平衡是一项昂贵的操作。

所以，我想知道对于这种设置，您更喜欢哪种数据结构。你有高维点，你想插入和查询最近的邻居。

Answer 1

Curse of Dimensionality 在这里碍手碍脚。您可能会考虑应用主成分分析 ( PCA ) 来降低维度，但据我所知，没有人对此有很好的答案。

我以前处理过这种类型的问题(在音频和视频指纹识别中)，有时多达 30 个维度。分析通常会发现一些维度不包含搜索的相关信息(实际上是模糊搜索，我的主要目标)，所以我从用于访问数据的索引结构中省略了它们，但将它们包含在逻辑中，以确定从一个在搜索过程中找到的候选人名单。这有效地将维度降低到易于处理的水平。

我通过严格量化剩余的维度进一步简化了事情，这样整个多维空间被映射到一个 32 位整数。我使用它作为 STL 映射(红黑树)中的键，尽管我可以使用哈希表。我能够在一两分钟内将数百万条记录动态添加到这种结构(当然基于 RAM)中，搜索平均花费大约一毫秒，尽管数据绝不是均匀分布的。搜索需要仔细枚举映射到 32 位 key 的维度中的值，但足够可靠以用于商业产品。如果我的资料来源正确，我相信它在 iTunes Match 中一直使用到今天。 :)

最重要的是，我建议您查看您的数据并进行一些自定义操作，利用其中的功能进行快速索引和搜索。找出变化最大且彼此最独立的维度。量化这些并将它们用作索引中的键。索引中的每个桶都包含共享该键的所有项目(可能不止一个)。要查找最近的邻居，请查看“附近”键并在每个存储桶中查找附近的值。祝你好运。

附言我写了一篇关于我的技术的论文，可用 here 。对付费墙感到抱歉。也许您可以在其他地方找到免费副本。如果您对此有任何疑问，请告诉我。