ADC 非对称距离计算

非对称距离计算 (Asymmetric Distance Computation, ADC) 是乘积量化 (PQ) 检索中用于高速评估未量化查询向量 $q \in \mathbb{R}^D$ 与已量化数据库向量 $\hat{x} \in \mathbb{R}^D$ 之间欧氏距离/点积的查表算法；在检索开始时，算法预先计算 $q$ 的各个子向量 $q_m$ 与对应子码本中 $K=256$ 个质心 $c_{m, k}$ 的距离填入查找表 (Look-Up Table, LUT: 大小 $M \times 256$)，对库中任意向量距离计算只需执行 $M$ 次查表与累加 $\sum_{m=1}^M \text{LUT}[m][\text{code}_m]$。

向量数据库 (Faiss, Milvus) 在 IVF-PQ 倒排桶内对百万候选向量进行百微秒级快速暴力扫描排序。

若将查询向量 $q$ 也量化后再算对称距离 (SDC)，会引入两次量化误差导致精度断崖式下跌；ADC 保持查询向量 $q$ 的完整浮点精度，只对库中数据量化，将每次 $D$ 维浮点乘加降维为仅 $M$ 次纳秒级查表累加，吞吐提升 20x+ 且有效控制量化误差。

推导 ADC 距离计算公式 $d(q, \hat{x})^2 = \sum_{m=1}^M \|q_m - c_{m, \text{code}_m(x)}\|^2$ 及其计算复杂度？

为什么预构建 LUT (查找表) 的时间复杂度为 $O(M \cdot K \cdot d^*) = O(K \cdot D)$，对单次 Query 延迟几乎可以忽略？

比较 ADC 与 SDC (对称距离计算) 在内存缓存命中率与重构精度上的量化差异？

如何利用 CPU SIMD (AVX2 / AVX-512 `_mm256_shuffle_epi8` / `_mm512_permutexvar_epi8`) 指令实现并行 16 字节 LUT 批量查表？

在 GPU 平台上执行 Batched ADC 扫描时，LUT 表如何布局以最大化 Warp 共享内存 (Shared Memory) 的无冲突访问？