🤖 AI 应用工程ID: adc-distance-computation

ADC 非对称距离计算

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

【ADC 非对称距离计算 核心考点 1】推导 ADC 距离计算公式 $d(q, \hat{x})^2 = \sum_{m=1}^M \|q_m - c_{m, \text{code}_m(x)}\|^2$ 及其计算复杂度？。技术解析：定义: 非对称距离计算 (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_{... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

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

【ADC 非对称距离计算 核心考点 2】为什么预构建 LUT (查找表) 的时间复杂度为 $O(M \cdot K \cdot d^*) = O(K \cdot D)$，对单次 Query 延迟几乎可以忽略？。技术解析：定义: 非对称距离计算 (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_{... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

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

【ADC 非对称距离计算 核心考点 3】比较 ADC 与 SDC (对称距离计算) 在内存缓存命中率与重构精度上的量化差异？。技术解析：定义: 非对称距离计算 (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_{... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

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

【ADC 非对称距离计算 核心考点 4】如何利用 CPU SIMD (AVX2 / AVX-512 `_mm256_shuffle_epi8` / `_mm512_permutexvar_epi8`) 指令实现并行 16 字节 LUT 批量查表？。技术解析：定义: 非对称距离计算 (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_{... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

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

【ADC 非对称距离计算 核心考点 5】在 GPU 平台上执行 Batched ADC 扫描时，LUT 表如何布局以最大化 Warp 共享内存 (Shared Memory) 的无冲突访问？。技术解析：定义: 非对称距离计算 (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_{... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

ADC Asymmetric Distance Computation

🎯核心定义

非对称距离计算 (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+ 且有效控制量化误差。

🎯5 个高频面试考点 (Exam Points)

推导 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) 的无冲突访问？

📖 关联深度指南:📄 vector-databases-and-hnsw →

更新于 2026-08-14

🎯

检验攻克程度：针对「ADC 非对称距离计算」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。

🚀 开始本考点专项刷题 ➔

← 上一个知识点PQ 乘积量化与码本聚类下一个知识点 →IVF 倒排网格与残差量化

🔗 更多 AI 应用工程知识点卡片

向量距离度量与 L2 归一化 SQ8/SQ4 标量量化 HNSW 跳表多层图结构 HNSW 启发式邻居选择与路由

ADC 非对称距离计算

🔗 更多 AI 应用工程 知识点卡片

🔗 更多 AI 应用工程知识点卡片