看本文前，先看一下：Composite Quantization for Approximate Nearest Neighbor Search

在此基础上：

• 引入了两个可选的目标函数：一个来自严格正交性约束，另一个来自广义三角形不等式
• 对CQ进行了更广泛的分析，包括为什么量化适合于近似最近邻搜索，为什么使用多个不同的字典而不是单个字典、与AQ&RVQ的关系。
• 进行了更多的实验，例如量化移动搜索的查询，以及内部产品相似性搜索。

简介

介绍了一种复合量化框架。见 CQ(2014)。

关键贡献：引入了近似正交性约束——近正交复合量化。

证明了近正交复合量化和最小化函数上限之间的等价性。

展示了在其他三个应用中的优越性能：与反向多索引的组合、移动搜索的量化查询和内积相似性搜索。

具体地，

• 本文首先通过引入正交性约束（即字典相互正交），提出了一种称为正交复合量化的朴素解决方案。—— $\epsilon = 0$

优点：可以从查询到每个选定元素的距离来计算近似距离，只需进行几个距离表查找，并且时间成本从O（D）减少到O（M）。

• 再提出了一种更好的解决方案，称为近正交复合量化(NOCQ)，通过将正交性约束放宽为近正交性约束，即用于近似向量但来自不同字典的所有元素对的内积的总和是恒定的。—— $\epsilon \not= 0$

优点：距离近似更准确，搜索精度更高。

背景介绍

ANNS 算法两大分类：

• 通过索引结构将查询与一小部分参考向量进行比较来加速搜索