Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces

By Wei Dong, Moses Charikar, Kai Li. 2008

116 citations recorded by the source corpus.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition, Information Retrieval & Search, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

In Representation & Self-Supervised Learning

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “Prior to our work, asymmetry was applied for hashing higher order similarity [22], sketching [8], hashing different subspaces [3], and data dependent hashing [20] which unlike locality sensitive hashing do not come with provable runtime guarantees.”
Asymmetric metric learning for knowledge transfer (2020, background): “Asymmetry Asymmetric distances or similarities are common in approximate nearest neighbor search, where queries may be quantized differently than the database, or not at all [12, 17, 34, 32, 45, 10].”
Hierarchical semantic indexing for large scale image retrieval (2011, background): “Significant work has been done on hashing for the related problem of finding approximate nearest neighbors [1, 9 ]. In our setting, retrieval using bilinear similarity on vectors of probabilities is a core subroutine, and we introduce a novel hashing scheme to accomplish this.”
The Power of Asymmetry in Binary Hashing (2013, background): “This has become known as “asymmetric hashing” [2, 4], but even with such a-symmetry, both mappings are based on the same fractional mapping f̃(·).”
Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, methodology): “Prior to our work, asymmetry was applied for hashing higher order similarity [22], sketching [8], hashing different subspaces [3], a nd data dependent hashing [20] which unlike locality sensitive hashing do not come with provable runtime guarantees.”
Hamming Distance Metric Learning (2012, methodology): “To break ties and improve the similarity measure, previous work suggests the use of an asymmetric Hamming (AH) distance [9, 14].”
Learning Binary Codes for Maximum Inner Product Search (2015, methodology): “1An asymmetric LSH algorithm with sketches [5] was previously proposed at a early stage.”
Polysemous Codes (2016, background): “This problem is partially solved by asymmetric variants of LSH [16,26,22], whose estimations use compact codes for database vectors but not on the query side.”
Optimized Product Quantization (2014, unknown): “We notice other ways of asymmetric Hamming (AH) distance [29], [30] have been developed.”
Large Scale Visual Recognition (2012, background): “The key is to construct on a family of hash functions H such that Pr h∈H (h(x) = h(y)) = Sim(x, y) [123] or Pr(h1(x) = h2(y)) = Sim(x, y) with h1 and h2 drawn independently [116].”
High-Dimensional Sparse Cross-Modal Hashing with Fine-Grained Similarity Embedding (2021, methodology): “Therefore, we adopt an asymmetric strategy [7, 10, 14] to solve the optimization problem.”