在Faiss核心技术一文中我以IndexFlatL2为例解释了Faiss的工作原理。IndexFlatL2只是个距离索引，它把数据库向量的L2 norm提前算好，虽然可以减少向量搜索过程中的计算量，但效果终究有限，更重要的是，它无法避免需要对整个数据库做穷举搜索。
因此本文将会介绍另一个基础索引，IndexIVFFlat，它会做些一个索引真正该做的事儿：少做事情才会快。
Overview
IVF（Inverted File Index）是一种数据库预处理技术，先把数据库中所有向量通过K-means聚类算法划分成多个簇，后续在进行数据库搜索时，先找出与目标向量（query）所对应的目标簇，再在簇内做穷举比对。
还是拿图像检索来举例，假设数据库里有10K张图片，IndexIVFFlat先把这些图片train（划分）成100个簇，当需要搜索一张猴子图片时，只需搜索动物类簇即可，这样一来，向量比对次数就从原本的10K变成了200（100 + 10K / 100），减少了将近2个数量级。
Clustering
IndexIVFFlat通过K-means聚类算法为数据库建立簇索引（上图中的quantizer），索引中的data（centroids）是各簇的中心向量，目标向量和哪个centroid最接近就属于哪个簇。
k-means算法如图示，先从数据库随机（不重复）挑选出N个向量作为簇索引的初始centroids，接着通过不断地迭代优化（or训练 ）centroids：
- 为centroids创建一个距离索引（IndexFlatL2），然后为数据库里的每个向量找出它所属的簇。
- 将同一簇的所有向量作加权求和，然后用它作为该簇的新centroid。
- 回到第一步，进行下一轮迭代。
Search
IndexIVFFlat的搜索过程分为两步，先是通过簇索引来搜索出query所属的簇，再在该簇内做穷举比对。搜索过程依旧是通过IndexFlatL2来计算向量间的距离，然后找出距离最接近的K个元素，这在前文Faiss核心技术有详细介绍，这里不再赘述。
Next
虽然IndexIVFFlat在搜索时的计算虽然只涉及数据库的一部分，但终究还是要存储整个数据库，这不仅费内存，更重要的是会导致memory bound。假设数据库里有256M个向量，向量长度是1024维，数据类型是fp32，那这个数据库大小就是1TB，划分为256个簇，每个簇就有4GB！
Faiss提供了一种量化索引：IndexIVFPQ，它可以量化压缩索引中的数据库向量（centroids），在搜索时再解压缩使用，相关的详细介绍可以看这篇博文Product Quantizers for k-NN Tutorial Part 1。
Conclusion
IndexIVFFlat虽然可以将向量比对缩小在一个簇的范围内，但终究还是要计算向量间距离，这样就需要在索引中维护整个数据库原始数据，而IndexIVFPQ通过压缩/解压缩向量的方式减轻了对内存带宽的需求。
欢迎关注和点赞，你的鼓励将是我创作的动力
欢迎转发至朋友圈，公众号转载请后台留言申请授权～
