本文提出了一种新的紧凑编码方法——复合量化，用于近似近邻搜索。
想法：利用从字典中选择的几个元素的组成来准确地近似一个向量——获得更小的 distortion errors，并通过由所选元素的索引组成的短代码来表示该向量。
引入了一个额外的约束条件——来自不同字典的所有元素对的内积之和为常数，使近似距离仅使用查询与每个选定元素的距离就足以进行近邻搜索。
提出了一种可以同时找到字典和压缩码的优化算法。
PQ和笛卡尔k-means可以被视为该方法的约束版本。
树——许多数据结构和算法被开发来消除距离计算的数量。例如，使用k-d树算法通过限制搜索时间来查找ann。
哈希、ITQ——将数据库向量转换为短码的算法由于其存储成本小，使得在内存中搜索可行，并且距离计算成本也降低。但汉明嵌入算法只能产生几个不同的距离，导致距离逼近的能力和灵活性有限。
PQ——将空间分解为低维子空间的笛卡尔积，并分别量化每个子空间。然后用一个由它的子空间量化指标组成的短代码表示一个向量。查询和数据库向量之间的距离通过使用查询和对应于数据库向量的短代码来近似计算。使可能距离的数量显著增加，因此距离近似更准确。
笛卡尔k-means 、OPQ——通过找到更好的子空间划分来改进产品量化，并实现更好的搜索性能。
查询向量： $q ∈ R^d$
N个d维向量： $\mathcal{X} = \{x_1, . . . , x_N \}$
向量x用M个元素表示： $\{c_{1k_1} , c_{2k_2} , . . . , c_{Mk_M} \}$
一个字典用K个元素组成： $C_m =\{c_{m1}, . . . , c_{mK} \}$