Content deleted Content added
rewrite with more references |
fill in OPQ section briefly |
||
Line 2:
'''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 |url=https://ieeexplore.ieee.org/abstract/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 |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 |arxiv=1908.10396 }}</ref>
Product quantization can be used by itself or as a component of more complex ANN search algorithms.<ref name="douze2024faiss">{{cite arXiv |arxiv=2401.08281}}</ref> The combination of product quantization with inverted files is sometimes known as IVFDAC (inverted file system with asymmetric distance computation): this involves dividing the database into coarse buckets and, for a given query, doing distance computations only with the buckets nearest to that query.<ref name="matsui2018survey">{{cite journal |last1=Matsui |first1=Yusuke |last2=Uchida |first2=Yusuke |last3=Jégou |first3=Hervé |last4=Satoh |first4=Shin'ichi |title=A Survey of Product Quantization |journal=ITE Transactions on Media Technology and Applications |date=2018 |volume=6 |issue=1 |pages=2–10 |doi=10.3169/mta.6.2 |url=https://www.jstage.jst.go.jp/article/mta/6/1/6_2/_article/-char/ja/ |access-date=13 April 2025}}</ref>
=== Optimized product quantization (OPQ) ===
Optimized product quantization is a widely used enhancement which applies a [[rotation matrix]] before quantizing vectors, in order to better take into account the data distribution.<ref name="matsui2018survey"></ref>
{{Drafts moved from mainspace|date=March 2025}}
| |||