IVF-Flat#
IVF-Flat 是一种倒排文件索引 (IVF) 算法，在最近邻搜索的上下文中，这意味着数据点被划分到多个聚类中。在搜索时，仅在最近的（用户定义的）聚类子集中执行暴力搜索。实际上，该算法搜索索引的速度比暴力搜索快得多，并且通常仍能保持可接受的召回率，但这也有一个缺点，即索引本身将原始训练向量复制到针对快速内存读取优化的内存布局中，并增加了一些额外的内存存储开销。索引训练完成后，此算法不再需要原始的训练向量数据。
IVF-Flat 通常是以下情况下的绝佳选择：
1. 像暴力搜索一样，有足够的设备内存来容纳索引中的所有向量，并且 2. 不需要精确召回。与其他索引类型一样，调优参数用于权衡召回率与搜索延迟/吞吐量。
[ C API | C++ API | Python API | Rust API ]
过滤考量#
IVF 方法仅将过滤器应用于对每个查询点探测的列表。因此，过滤查询的结果很可能与应用于暴力搜索等精确方法的过滤结果显着不同。例如，假设您有 3 个 IVF 列表，每个列表包含 2 个向量，并且您仅对最近的 2 个列表执行查询，但您过滤掉了除 1 个元素之外的所有元素。如果剩下的那个元素恰好在未被探测的列表中，那么它根本不会被考虑在搜索结果中。在使用任何 IVF 方法时，考虑这一点很重要。
配置参数#
构建参数#
名称 |
默认值 |
描述 |
|---|---|---|
n_lists |
sqrt(n) |
用于划分索引的粗略聚类数量。此值的一个良好启发式方法是 sqrt(索引中的向量数量) |
add_data_on_build |
True |
索引构建后是否应将训练点添加到索引中？ |
kmeans_train_iters |
20 |
k-means 训练达到收敛前的最大迭代次数。请注意，收敛可能在此迭代次数之前发生。 |
kmeans_trainset_fraction |
0.5 |
从原始数据集子采样用于训练 k-means 聚类的点比例。默认值为训练数据集的 1/2。对于非常大的数据集，通常可以减小此值，以提高聚类质量和构建时间。 |
adaptive_centers |
false |
现有的已训练质心是否应适应添加到索引中的新点？这提供了在牺牲计算新质心以提高召回率之间的权衡，当添加新点时需要为聚类计算新质心。当批量添加大量点时，性能开销可能不明显。 |
conservative_memory_allocation |
false |
为了支持动态索引（预计稍后会添加点），可以有意地预先对单个 IVF 列表进行过度分配，以减少和影响列表大小增加带来的影响，这需要分配更多内存并将旧列表复制到新的更大列表中。 |
搜索参数#
名称 |
默认值 |
描述 |
|---|---|---|
n_probes |
20 |
对每个查询点要扫描的最近 IVF 列表数量。 |
调优考量#
由于 IVF 方法使用聚类来建立空间局部性并将数据点划分到单独的列表中，因此有一个内在的假设是列表数量以及索引中数据的最大大小是预先知道的。对于某些用例，这可能不重要。例如，大多数矢量数据库会构建许多较小的物理近似最近邻索引，每个索引都来自固定大小或最大大小的不可变段，因此可以根据索引中的向量数量来调整列表数量。
根据经验，我们发现 \(\sqrt{n\_index\_vectors}\) 是 \(n\_lists\) 超参数的一个良好起点。请记住，列表越多意味着在每个列表中搜索的点越少，但也可能意味着在搜索时需要更多的 \(n\_probes\) 才能达到可接受的召回率。
内存占用#
每个聚类至少填充到 32 个向量（但可能高达 1024 个）。假设向量/列表均匀随机分布，我们将有 \(cluster\_overhead = (conservative\_memory\_allocation ? 16 : 512 ) * dim * sizeof_{float}\)
请注意，每个聚类都作为单独的分配进行分配。如果我们使用一个 cuda_memory_resource，它会以 1 MiB 的块获取内存，因此平均每个聚类可能有 0.5 MiB 的开销。如果我们使用数万个聚类，使用池分配器来避免这种开销就变得至关重要。
\(cluster\_overhead = 0.5 MiB\) // 如果不使用池分配器
索引（设备内存）：#
索引构建的设备内存峰值使用量：#
\(workspace = min(1GB, n\_queries * [(n\_lists + 1 + n\_probes * (k + 1)) * sizeof_{float} + n\_probes * k * sizeof_{idx}])\)
\(index\_size + workspace\)