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

• $ε$-VAE: Denoising as Visual Decoding [61.29255979767292]
  In generative modeling, tokenization simplifies complex data into compact, structured representations, creating a more efficient, learnable space. Current visual tokenization methods rely on a traditional autoencoder framework, where the encoder compresses data into latent representations, and the decoder reconstructs the original input. We propose denoising as decoding, shifting from single-step reconstruction to iterative refinement. Specifically, we replace the decoder with a diffusion process that iteratively refines noise to recover the original image, guided by the latents provided by the encoder. We evaluate our approach by assessing both reconstruction (rFID) and generation quality (
  arXiv  Detail & Related papers  (2024-10-05T08:27:53Z)
• 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)
• 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)
• Improving Code Search with Hard Negative Sampling Based on Fine-tuning [15.341959871682981]
  We introduce a cross-encoder architecture for code search that jointly encodes the concatenation of query and code. We also introduce a Retriever-Ranker (RR) framework that cascades the dual-encoder and cross-encoder to promote the efficiency of evaluation and online serving.
  arXiv  Detail & Related papers  (2023-05-08T07:04:28Z)
• 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.