# Metric Embedding into the Hamming Space with the n-Simplex Projection

@inproceedings{Vadicamo2019MetricEI, title={Metric Embedding into the Hamming Space with the n-Simplex Projection}, author={Lucia Vadicamo and Vladimir Mic and F. Falchi and Pavel Zezula}, booktitle={SISAP}, year={2019} }

Transformations of data objects into the Hamming space are often exploited to speed-up the similarity search in metric spaces. Techniques applicable in generic metric spaces require expensive learning, e.g., selection of pivoting objects. However, when searching in common Euclidean space, the best performance is usually achieved by transformations specifically designed for this space. We propose a novel transformation technique that provides a good trade-off between the applicability and the… Expand

#### One Citation

On the Similarity Search With Hamming Space Sketches

- Computer Science
- 2021

Various challenges of the similarity search with sketches in the Hamming space are addressed, including the definition of sketching transformation and efficient search algorithms that exploit sketches to speed up searching. Expand

#### References

SHOWING 1-10 OF 23 REFERENCES

Hilbert Exclusion: Improved Metric Search through Finite Isometric Embeddings

- Computer Science
- TOIS
- 2016

It is shown that many common metric spaces, notably including those using Euclidean and Jensen-Shannon distances, also have a stronger property, sometimes called the four-point property, and one in particular, which is named the Hilbert Exclusion property, allows any indexing mechanism which uses hyperplane partitioning to perform better. Expand

Supermetric Search

- Computer Science
- Inf. Syst.
- 2019

A full investigation into the use of the supermetric property within a variety of different hyperplane partition indexing structures is presented, and some more of its flexibility is shown by examining a search structure whose partition and exclusion conditions are tailored, at each node, to suit the individual reference points and data set present there. Expand

High-Dimensional Simplexes for Supermetric Search

- Computer Science, Mathematics
- SISAP
- 2017

The n-point property is a generalisation of triangle inequality where, for any \((n+1)\) objects in the space, there exists an n-dimensional simplex whose edge lengths correspond to the distances among the objects. Expand

Selecting Sketches for Similarity Search

- Computer Science
- ADBIS
- 2018

This work proposes a way to efficiently estimate the quality of sketches using just a small sample set of data based on a probabilistic analysis of sketches which describes how separated are objects after projection to the Hamming space. Expand

Effective Proximity Retrieval by Ordering Permutations

- Computer Science, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 2008

A new probabilistic proximity search algorithm for range and A"-nearest neighbor (A"-NN) searching in both coordinate and metric spaces is introduced to predict closeness between elements according to how they order their distances toward a distinguished set of anchor objects. Expand

Asymmetric Distances for Binary Embeddings

- Mathematics, Computer Science
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 2011

This work proposes two general asymmetric distances that are applicable to a wide variety of embedding techniques including locality sensitive hashing (LSH), locality sensitive binary codes (LSBC), spectral hashing (SH), PCA embedding (PCA), PCAE with random rotations (PCAE-RR), and PCA with iterative quantization (PCae-ITQ). Expand

Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval

- Mathematics, Medicine
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- 2013

This paper addresses the problem of learning similarity-preserving binary codes for efficient similarity search in large-scale image collections by proposing a simple and efficient alternating minimization algorithm, dubbed iterative quantization (ITQ), and demonstrating an application of ITQ to learning binary attributes or "classemes" on the ImageNet data set. Expand

Binary Sketches for Secondary Filtering

- Computer Science
- ACM Trans. Inf. Syst.
- 2019

This article proposes an approach to enhancing the existing search techniques to significantly reduce the number of accessed data objects while preserving the quality of the search results, and provides a probabilistic model to tune the parameters of the sketch-based filtering separately for each query object. Expand

Polysemous Codes

- Computer Science
- ECCV
- 2016

Polysemous codes are introduced, which offer both the distance estimation quality of product quantization and the efficient comparison of binary codes with Hamming distance, and their design is inspired by algorithms introduced in the 90's to construct channel-optimized vector quantizers. Expand

Aggregating local descriptors into a compact image representation

- Mathematics, Computer Science
- 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition
- 2010

This work proposes a simple yet efficient way of aggregating local image descriptors into a vector of limited dimension, which can be viewed as a simplification of the Fisher kernel representation, and shows how to jointly optimize the dimension reduction and the indexing algorithm. Expand