Similarity estimation techniques from rounding algorithms

By Moses Charikar. 2002

2,790 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Computer Vision and Pattern Recognition, Information Retrieval & Search

How researchers see this paper

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

In Artificial Intelligence

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data, and Web Data Only (2023, methodology): “For fuzzy duplicates, methods based on locally-sensitive hashes such as MinHash (Broder, 1997) or SimHash (Charikar, 2002) have been adopted for the pretraining data of large language models (Brown et al., 2020; Zeng et al., 2021; Rae et al., 2021).”
Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “, sign random projections (SRP) [10, 3]) or 2-bit coding are often better compared to using more bits.”
Unbounded cache model for online language modeling with open vocabulary (2017, methodology): “One of the most popular strategies is Locality-sensitive hashing (LSH) by Charikar [11], which uses random projections to approximate the cosine similarity between vectors by a function related to the Hamming distance between their corresponding binary codes.”
FastText.zip: Compressing text classification models (2016, methodology): “Several approaches derived from LSH have been recently proposed to achieve this goal, such as Asymmetric LSH by Shrivastava & Li (2014), subsequently discussed by Neyshabur & Srebro (2015).”
The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset (2023, methodology): “To remove near duplicate documents in OSCAR (which is already exact-deduplicated) we initially used SimHash (Charikar, 2002; Manku et al., 2007), a hashing function that associates to two similar texts hashes with a low Hamming distance, with 6-grams and a Hamming distance threshold of 4.”
From Frequency to Meaning: Vector Space Models of Semantics (2010, background): “Definitions of LSH functions include the Min-wise independent function, which preserves the Jaccard similarity between vectors (Broder, 1997), and functions that preserve the cosine similarity between vectors (Charikar, 2002).”
Lenient Multi-Agent Deep Reinforcement Learning (2017, background): “SimHash [7], a locality-sensitive hashing (LSH) function, can be applied to the rounded output of the dense layer to generate a hash-key φ for a state s .”
Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality (2012, methodology): “This approach has been useful for variants of edit distance [49, 25, 24, 20, 51], earth-mover distance [21, 37, 28, 5] and other metrics.”
Orthogonal Random Features (2016, methodology): “In the appendix, we show empirically that the same scheme can be successfully applied to angle estimation where the nonlinear map f is a non-smooth sign(·) function [4].”
On Symmetric and Asymmetric LSHs for Inner Product Search (2014, methodology): “M L ] 2 4 O ct 2 01 4”
Kernelized locality-sensitive hashing for scalable image search (2009, methodology): “To perform the approximate similarity searches, we use the method in [3], which requires searching O(n) examples for thek = 1 approximate-NN.”
Google news personalization: scalable online collaborative filtering (2007, background): “This similarity measure, also known as the Jaccard coefficient, takes values between 0 and 1 and it is well known that the corresponding distance function D(ui, uj) = 1 − S(ui, uj) is a metric [6].”
Single cell RNA-seq data clustering using TF-IDF based methods (2018, methodology): “In ongoing work we are exploring MinHashing [25, 26] and Locality Sensitive Hashing (LSH) [27–30] techniques that make feasible the efficient computation of highly similar pairs of cells under, e.”
Privacy-Preserving Machine Learning for Speech Processing (2012, background): “…LSH constructions for a variety of distance metrics, including arbitrary kernels [Kulis and Grauman, 2009], but we mainly consider LSH for Euclidean distance (E2LSH) [Datar et al., 2004b] and cosine distance [Charikar, 2002a] as the LSH functions for these constructions are simply random vectors.”