🤖 AI EngineeringID: adc-distance-computation

ADC Asymmetric Distance Computation

Q: Derive the ADC distance formula $d(q, \hat{x})^2 = \sum_{m=1}^M \|q_m - c_{m, \text{code}_m(x)}\|^2$ and its computational complexity?

【ADC Asymmetric Distance Computation 核心考点 1】Derive the ADC distance formula $d(q, \hat{x})^2 = \sum_{m=1}^M \|q_m - c_{m, \text{code}_m(x)}\|^2$ and its computational complexity?。技术解析：Definition: Asymmetric Distance Computation (ADC) is a lookup-table acceleration algorithm in Product Quantization (PQ) that evaluates Euclidean distance or dot product between an unquantized query vector q \in \mathbb{R}^D and a quantized database vector \hat{x} \in \mathbb{R}^D... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

Q: Why is LUT pre-computation complexity $O(K \cdot D)$ negligible for single-query latency?

【ADC Asymmetric Distance Computation 核心考点 2】Why is LUT pre-computation complexity $O(K \cdot D)$ negligible for single-query latency?。技术解析：Definition: Asymmetric Distance Computation (ADC) is a lookup-table acceleration algorithm in Product Quantization (PQ) that evaluates Euclidean distance or dot product between an unquantized query vector q \in \mathbb{R}^D and a quantized database vector \hat{x} \in \mathbb{R}^D... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

Q: Quantify the differences between ADC and SDC in CPU L1/L2 cache hit rate and reconstruction accuracy?

【ADC Asymmetric Distance Computation 核心考点 3】Quantify the differences between ADC and SDC in CPU L1/L2 cache hit rate and reconstruction accuracy?。技术解析：Definition: Asymmetric Distance Computation (ADC) is a lookup-table acceleration algorithm in Product Quantization (PQ) that evaluates Euclidean distance or dot product between an unquantized query vector q \in \mathbb{R}^D and a quantized database vector \hat{x} \in \mathbb{R}^D... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

Q: How can CPU SIMD instructions (`_mm256_shuffle_epi8`) parallelize 16-byte LUT batch lookups?

【ADC Asymmetric Distance Computation 核心考点 4】How can CPU SIMD instructions (`_mm256_shuffle_epi8`) parallelize 16-byte LUT batch lookups?。技术解析：Definition: Asymmetric Distance Computation (ADC) is a lookup-table acceleration algorithm in Product Quantization (PQ) that evaluates Euclidean distance or dot product between an unquantized query vector q \in \mathbb{R}^D and a quantized database vector \hat{x} \in \mathbb{R}^D... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

Q: How should the LUT be organized in GPU shared memory to prevent bank conflicts during batched ADC scans?

【ADC Asymmetric Distance Computation 核心考点 5】How should the LUT be organized in GPU shared memory to prevent bank conflicts during batched ADC scans?。技术解析：Definition: Asymmetric Distance Computation (ADC) is a lookup-table acceleration algorithm in Product Quantization (PQ) that evaluates Euclidean distance or dot product between an unquantized query vector q \in \mathbb{R}^D and a quantized database vector \hat{x} \in \mathbb{R}^D... 完整推导与工程落地见：https://talentme.airsota.com/resources/tech/roadmap/mindmap/AI_Engineering/card/adc-distance-computation

ADC 非对称距离计算

🎯Core Definition

Asymmetric Distance Computation (ADC) is a lookup-table acceleration algorithm in Product Quantization (PQ) that evaluates Euclidean distance or dot product between an unquantized query vector

q \in \mathbb{R}^D

and a quantized database vector

\hat{x} \in \mathbb{R}^D

; at query onset, it pre-computes distances between query sub-vectors

q_m

and all

K=256

centroids

c_{m, k}

into a Look-Up Table (LUT: size

M \times 256

), enabling database vector distance estimation via

M

fast table lookups and additions

\sum_{m=1}^M \text{LUT}[m][\text{code}_m]

💡Use Cases

High-throughput scanning and re-ranking of millions of candidate vectors within IVF-PQ buckets in vector databases (Faiss, Milvus).

⚡Key Problems Solved

Symmetric Distance Computation (SDC) quantizes both query and database vectors, compounding quantization error and destroying recall; ADC retains full FP32 query precision, converting

D

floating-point multiplications into

M

nanosecond table lookups, multiplying scanning throughput by 20x+ with minimal error.

🎯5 High-Frequency Exam Points

Derive the ADC distance formula

d(q, \hat{x})^2 = \sum_{m=1}^M \|q_m - c_{m, \text{code}_m(x)}\|^2

and its computational complexity?

Why is LUT pre-computation complexity

O(K \cdot D)

negligible for single-query latency?

Quantify the differences between ADC and SDC in CPU L1/L2 cache hit rate and reconstruction accuracy?

How can CPU SIMD instructions (`_mm256_shuffle_epi8`) parallelize 16-byte LUT batch lookups?

How should the LUT be organized in GPU shared memory to prevent bank conflicts during batched ADC scans?

📖 In-depth Guide:📄 vector-databases-and-hnsw →

Updated 2026-08-14

🎯

Test Your Knowledge: Practice Questions for "ADC Asymmetric Distance Computation"

Single choice pitfall questions with instant feedback and mistake tracking.

🚀 Start Card Practice ➔

← Previous CardProduct Quantization (PQ)Next Card →IVF Inverted File Indexing

🔗 More AI Engineering Knowledge Cards

Vector Distance Metrics & L2 Normalization Scalar Quantization (SQ8/SQ4)HNSW Multi-Layer Skip Graph HNSW Heuristic Search & Routing