# OverView of ANN Pipeline
###### tags: `Product Quantizer`
[ToC]
### ANN是什么？
ANN，全称Approximate Nearest Neighbor，近似最近邻搜索，通常处理的对象是高维度向量。如果对向量不做任何处理，直接暴力算出欧式距离，然后找最大的，就是Nearest Neighbor，是所有ANN算法的上限。但是这么做一是要占据大量的内存来存储这些特征，另外是暴力搜索要计算query和所有gallery之间的高维向量距离，非常耗时。鉴于这两点，一般会对大库搜索进行一些处理进行特征压缩和加速搜索，同时会有一些性能损失，运用这些技术的搜索方法，可以统称为ANN。
### overview
#### 三个要考虑的因素
* 精度
* 速度
* 内存
最终目标是，牺牲最少的搜索精度，以换取尽可能快的搜索速度或者尽可能少的内存占用，或者使三者达到一个更好的trade-off点
#### pipeline
本文以[faiss](https://github.com/facebookresearch/faiss/wiki)部署的基本算法为脉络，讲解ANN的重要部件及其中一些原理


图中的实线框代表操作，虚线框代表产生的存储结果，主要包含两个过程：
* **建库**。将所有的gallery特征按照一定的规则进行压缩编码，方便后续的配套搜索方法进行快速搜索
* **搜索**。对于一个特定的query，按照和gallery配套的方法，进行处理，并通过一定方法找到其top 1或top k临近的样本。

有三个重要的模块在设计搜索算法时需要重点考虑：
* **Data Pre-process**。一般配套后面的量化器，都需要对数据进行维度平衡等操作。否则性能会很差,详细见[Data Pre-Process](https://hackmd.io/CJRugKyCQ6mhyE_kfrZGsw),建议先看量化器再看这个。
* **非穷举搜索**。为了在计算距离前过滤掉大部分不可能临近的数据，加速搜索，需要设计一个过滤器，本文以IVF为例进行讲解，和量化器写在一个文件里面。
* **量化器**。量化器是搜索算法的核心，作用是将原来的高维度float特征变成低位的int8或者bit型数据，在极大节省内存的情况下，同时可以用查找表，汉明距离等操作代替float乘累加来加速搜索。本文以经典的PQ（Product Quantizer）来说明，详细见[Product Quantizer](https://hackmd.io/c0kAkuQER-KqMC8COe1Mvg)。