  We present the multi-layer extension of the Sparse Ternary Codes (STC) for
fast similarity search where we focus on the reconstruction of the database
vectors from the ternary codes. To consider the trade-offs between the
compactness of the STC and the quality of the reconstructed vectors, we study
the rate-distortion behavior of these codes under different setups. We show
that a single-layer code cannot achieve satisfactory results at high rates.
Therefore, we extend the concept of STC to multiple layers and design the
ML-STC, a codebook-free system that successively refines the reconstruction of
the residuals of previous layers. While the ML-STC keeps the sparse ternary
structure of the single-layer STC and hence is suitable for fast similarity
search in large-scale databases, we show its superior rate-distortion
performance on both model-based synthetic data and public large-scale
databases, as compared to several binary hashing methods.
