Product tree quantization for approximate nearest neighbor search

The product quantization (PQ) performance degrades on read-world data due to the severity of dependence between feature groups. Meanwhile, tree structured vector quantization (TSVQ) often supply lower distortion than other structured vector quantizers; yet it is prohibitive to learning compact codes like PQ does considering its codebook storage. In this paper, we propose a hybrid model dubbed as product tree quantization (PTQ) that aims to relax the PQ constraints while to retain the tree-structured codebooks with reasonable size. We first show that our methods can achieve significantly better quantization performance on several large scale benchmarks. We then demonstrate the advantage for very large scale ANN search; for instance, on a 1-billion scale dataset, we have achieved on average 4% improvement in accuracy than the existing state of the art methods.