algorithm - Knn 搜索大数据？

Question

我有兴趣在大型数据集上执行 knn 搜索。

有一些库：ANN和FLANN，但我对这个问题很感兴趣：如果您的数据库不完全适合内存（RAM），如何组织搜索？

Answer 1

我想这取决于您的索引与内存相比有多大。这是我的第一个自发想法：

1. 假设它是 RAM 的数十倍，我会尝试使用例如层次聚类树（在 FLANN 中实现）对我的数据进行聚类。我会修改树的实现，以便它们将分支保存在内存中并将叶子（簇）保存在磁盘上。因此，每次都必须加载适当的集群。然后，您可以尝试以不同的方式对此进行优化。

2. 如果它不是那么大（假设是 RAM 的两倍），我会将数据集分成两部分并为每个部分创建一个索引。因此，我需要在每个数据集中找到最近的邻居，然后在它们之间进行选择。

Answer 2

这取决于您的数据是否非常高维。如果它是相对低维的，您可以使用现有的磁盘R-Tree实现，例如Spatialite。

如果是更高维度的数据，您可以使用X-Trees，但我不知道有任何磁盘上的实现。

或者，您可以使用磁盘持久性实现局部敏感散列，例如使用 mmap。