Approximate search with quantized sparse representations
This work addresses the challenge of scalable approximate nearest neighbor search for applications like image retrieval, but it is incremental as it builds on and generalizes existing methods like product or residual quantization.
The paper tackles the problem of efficiently storing and searching large vector collections, such as visual descriptors, by proposing quantized sparse coding, which approximates database vectors with constrained sparse representations using finite atom weights. Experiments on standard benchmarks, including BIGANN, show that this method achieves competitive performance in terms of learning/coding time, index size, and search quality.
This paper tackles the task of storing a large collection of vectors, such as visual descriptors, and of searching in it. To this end, we propose to approximate database vectors by constrained sparse coding, where possible atom weights are restricted to belong to a finite subset. This formulation encompasses, as particular cases, previous state-of-the-art methods such as product or residual quantization. As opposed to traditional sparse coding methods, quantized sparse coding includes memory usage as a design constraint, thereby allowing us to index a large collection such as the BIGANN billion-sized benchmark. Our experiments, carried out on standard benchmarks, show that our formulation leads to competitive solutions when considering different trade-offs between learning/coding time, index size and search quality.