Draft:Product quantization: Difference between revisions

Revision as of 18:44, 13 April 2025

Revision as of 14:14, 14 April 2025

Line 1:

{{Short description|Vector search algorithm}}

{{Draft topics|stem}}

{{AfC topic|stem}}

{{AfC submission|||ts=20250414141445|u=Osmarks|ns=118}}

{{Draft article}}

'''Product quantization''' ('''PQ''') is a technique for [[Nearest neighbor search#Approximation methods|approximate nearest neighbor]] search.<ref name="product2010jegou">{{cite journal |last1=Jégou |first1=Herve |last2=Douze |first2=Matthijs |last3=Schmid |first3=Cordelia |title=Product Quantization for Nearest Neighbor Search |journal=IEEE Transactions on Pattern Analysis and Machine Intelligence |date=2010-03-18 |volume=33 |issue=1 |pages=117–128 |doi=10.1109/TPAMI.2010.57 |pmid=21088323 |url=https://ieeexplore.ieee.org/document/5432202 |access-date=13 April 2025}}</ref> It works by [[lossy compression|lossily compressing]] vectors by representing them as a [[Cartesian product]] of [[Dimension_(vector_space) | low-dimensional]] [[Linear_subspace | subspaces]] and quantizing each subspace independently.<ref name="wu2019vector">{{cite journal |last1=Wu |first1=Ze-bin |last2=Yu |first2=Jun-qing |title=Vector quantization: a review |journal=Frontiers of Information Technology & Electronic Engineering |date=2019-05-18 |volume=20 |issue=4 |pages=507–524 |doi=10.1631/FITEE.1700833 |url=https://link.springer.com/article/10.1631/fitee.1700833}}</ref> Distances can be efficiently computed between product-quantized vectors and an unquantized vector by creating a [[lookup table]], so product quantization can save compute, storage and memory bandwidth.<ref name="guo2019accelerating">{{cite arXiv |eprint=1908.10396 |last1=Guo |first1=Ruiqi |last2=Sun |first2=Philip |last3=Lindgren |first3=Erik |last4=Geng |first4=Quan |last5=Simcha |first5=David |last6=Chern |first6=Felix |last7=Kumar |first7=Sanjiv |title=Accelerating Large-Scale Inference with Anisotropic Vector Quantization |date=2019 |class=cs.LG }}</ref>