Chain quantization (ChainQ)

Chain quantization (ChainQ)

Chain quantization (ChainQ) is an non-orthogonal MCQ method.

ChainQ uses codebooks that only have a dependency with the previous and next codebook, therefore creating a chain. This allows the use of efficient polynomial (max-product) algorithms to find optimal encoding.

Rayuela.quantize_chainq โ€” Function.
quantize_chainq(X, C, use_cuda=false, use_cpp=false) -> B, ellapsed

Given data and chain codebooks, find codes using the Viterbi algorithm chain quantizer.

Arguments

  • X::Matrix{T}: d-by-n data to quantize
  • C::Vector{Matrix{T}}: m-long vector with d-by-h matrices. Each matrix is a pretrained codebook of size approximately d-by-h.
  • use_cuda::Bool: whether to use a CUDA implementation
  • use_cpp::Bool: whether to use a c++ implementation

If both use_cuda and use_cpp are true, the CUDA implementation is used.

Returns

  • B::Matrix{Int16}: m-by-n matrix with the codes
  • ellapsed::Float64: The time spent encoding
source
Rayuela.train_chainq โ€” Function.
train_chainq(X, m, h, R, B, C, niter, V=false) -> C, B, R, error

Train a chain quantizer. This method is typically initialized by Optimized product quantization (OPQ)

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)
  • R::Matrix{T}: d-by-d rotation matrix for initialization
  • B::Matrix{Int16}: m-by-n matrix with pre-trained codes for initialization
  • C::Vector{Matrix{T}}: m-long vector with d-by-h matrices. Each matrix is a pretrained codebook of size approximately d-by-h.
  • niter::Integer: Number of 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-by-h.
  • B::Matrix{Int16}: m-by-n matrix with the codes
  • R::Matrix{T}: d-by-d optimized rotation matrix
  • error::T: The quantization error after training
source

Reference

Babenko, A., & Lempitsky, V. (2015). Tree quantization for large-scale similarity search and classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (pp. 4240-4248). [PDF]