Nearest neighbor search with compact codes: A decoder perspective
- URL: http://arxiv.org/abs/2112.09568v1
- Date: Fri, 17 Dec 2021 15:22:28 GMT
- Title: Nearest neighbor search with compact codes: A decoder perspective
- Authors: Kenza Amara, Matthijs Douze, Alexandre Sablayrolles, Herv\'e J\'egou
- Abstract summary: We re-interpret popular methods such as binary hashing or product quantizers as auto-encoders.
We design backward-compatible decoders that improve the reconstruction of the vectors from the same codes.
- Score: 77.60612610421101
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Modern approaches for fast retrieval of similar vectors on billion-scaled
datasets rely on compressed-domain approaches such as binary sketches or
product quantization. These methods minimize a certain loss, typically the mean
squared error or other objective functions tailored to the retrieval problem.
In this paper, we re-interpret popular methods such as binary hashing or
product quantizers as auto-encoders, and point out that they implicitly make
suboptimal assumptions on the form of the decoder. We design
backward-compatible decoders that improve the reconstruction of the vectors
from the same codes, which translates to a better performance in nearest
neighbor search. Our method significantly improves over binary hashing methods
or product quantization on popular benchmarks.
Related papers
- Breadth-first graph traversal union-find decoder [0.0]
We develop variants of the union-find decoder that simplify its implementation and provide potential decoding speed advantages.
We show how these methods can be adapted to decode non-topological quantum low-density-parity-check codes.
arXiv Detail & Related papers (2024-07-22T18:54:45Z) - Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
Low-Density Parity-Check codes possess several advantages over other families of codes.
The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
arXiv Detail & Related papers (2024-06-09T12:08:56Z) - Progressive-Proximity Bit-Flipping for Decoding Surface Codes [9.801253635315636]
Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation.
Existing decoders often fall short of meeting requirements such as having low computational complexity.
We propose a novel bit-flipping (BF) decoder tailored for toric and surface codes.
arXiv Detail & Related papers (2024-02-24T22:38:05Z) - Sparse-Inductive Generative Adversarial Hashing for Nearest Neighbor
Search [8.020530603813416]
We propose a novel unsupervised hashing method, termed Sparsity-Induced Generative Adversarial Hashing (SiGAH)
SiGAH encodes large-scale high-scale high-dimensional features into binary codes, which solves the two problems through a generative adversarial training framework.
Experimental results on four benchmarks, i.e. Tiny100K, GIST1M, Deep1M, and MNIST, have shown that the proposed SiGAH has superior performance over state-of-the-art approaches.
arXiv Detail & Related papers (2023-06-12T08:07:23Z) - Efficient k-NN Search with Cross-Encoders using Adaptive Multi-Round CUR
Decomposition [77.4863142882136]
Cross-encoder models are prohibitively expensive for direct k-nearest neighbor (k-NN) search.
We propose ADACUR, a method that adaptively, iteratively, and efficiently minimizes the approximation error for the practically important top-k neighbors.
arXiv Detail & Related papers (2023-05-04T17:01:17Z) - Efficient Nearest Neighbor Search for Cross-Encoder Models using Matrix
Factorization [60.91600465922932]
We present an approach that avoids the use of a dual-encoder for retrieval, relying solely on the cross-encoder.
Our approach provides test-time recall-vs-computational cost trade-offs superior to the current widely-used methods.
arXiv Detail & Related papers (2022-10-23T00:32:04Z) - Unsupervised Semantic Hashing with Pairwise Reconstruction [22.641786533525245]
We present Pairwise Reconstruction (PairRec), which is a discrete variational autoencoder based hashing model.
We experimentally compare PairRec to traditional and state-of-the-art approaches, and obtain significant performance improvements in the task of document similarity search.
arXiv Detail & Related papers (2020-07-01T10:54:27Z) - Pairwise Supervised Hashing with Bernoulli Variational Auto-Encoder and
Self-Control Gradient Estimator [62.26981903551382]
Variational auto-encoders (VAEs) with binary latent variables provide state-of-the-art performance in terms of precision for document retrieval.
We propose a pairwise loss function with discrete latent VAE to reward within-class similarity and between-class dissimilarity for supervised hashing.
This new semantic hashing framework achieves superior performance compared to the state-of-the-arts.
arXiv Detail & Related papers (2020-05-21T06:11:33Z) - Auto-Encoding Twin-Bottleneck Hashing [141.5378966676885]
This paper proposes an efficient and adaptive code-driven graph.
It is updated by decoding in the context of an auto-encoder.
Experiments on benchmarked datasets clearly show the superiority of our framework over the state-of-the-art hashing methods.
arXiv Detail & Related papers (2020-02-27T05:58:12Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.