VECTOR COMPRESSION FOR SIMILARITY SEARCH USING MULTI-LAYER SPARSE TERNARY CODES

摘要

It was shown recently that Sparse Ternary Codes (STC) posses superior “coding gain” compared to the classical binary hashing framework and can successfully be used for large-scale search applications. This work extends the STC for compression and proposes a rate-distortion efficient design. We first study a single-layer setup where we show that binary encoding intrinsically suffers from poor compression quality while STC, thanks to the flexibility in design, can have near-optimal rate allocation. We further show that single-layer codes should be limited to very low rates. Therefore, in order to target arbitrarily high rates, we adopt a multi-layer solution inspired by the classical idea of residual quantization. The proposed architecture, while STC in nature and hence suitable for similarity search, can add the “list-refinement” technique as a useful element to the similarity search setup. This can be achieved thanks to the excellent rate-distortion performance of this scheme which we validate on synthetic, as well as large-scale public databases.