Product quantization (PQ)

Product quantization (PQ)

Product quantization is an orthogonal MCQ method that uses $k$-means as its main subroutine.

Rayuela.quantize_pq — Function.
quantize_pq(X, C, V=false) -> B

Given data and PQ codeboks, quantize.

Arguments

  • X::Matrix{T}: d-by-n data to quantize
  • C::Vector{Matrix{T}}: m-long vector with d/m-by-h matrix entries. Each matrix is a PQ codebook.
  • V::Bool: Whether to print progress

Returns

  • B::Matrix{Int16}: m-by-n matrix with the codes that approximate X
source
Rayuela.train_pq — Function.
train_pq(X, m, h, niter=25, V=false) -> C, B, error

Trains a product quantizer.

Arguments

  • X::Matrix{T}: d-by-n data to quantize
  • m::Integer: Number of codebooks
  • h::Integer: Number of entries in each codebook (typically 256)
  • niter::Integer: Number of k-means iterations to use
  • V::Bool: Whether to print progress

Returns

  • C::Vector{Matrix{T}}: m-long vector with d-by-h matrix entries. Each matrix is a codebook of size approximately d/m-by-h.
  • B::Matrix{Int16}: m-by-n matrix with the codes
  • error::T: The quantization error after training
source

Reference

Jégou, H., Douze, M., & Schmid, C. (2011). Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1), 117-128. [PDF]