Fast locality-sensitive hashing

By Anirban Dasgupta, Ravi Kumar, Tamás Sarlós. 2011

170 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Information Retrieval & Search, Optimization & Training

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 Vision and Pattern Recognition

In Information Retrieval & Search

In Optimization & Training

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, methodology): “s (b-bit) minwise hashing and one permutation hashing [3, 24]. • Fast hashing for MIPS: Our proposed hash function uses random projection as the main hashing scheme. There is a rich set of literature [21, 1, 8, 24, 29] on making hashing faster. Evaluations of these new faster techniques will further”
Recent advances in convolutional neural networks (2015, background): “x. The space complexity of Adaptive Fastfood transform is O (n ), and the time complexity is O (n log n ). Motivated by the great advantages of circulant matrix in both space and computation eciency [166, 167], Cheng et al . [168] explore the redundancy in the parametrization of fully-connected laye”
Fastfood: Approximate Kernel Expansions in Loglinear Time (2014, background): “Lemma 6 (Computational Eﬃciency) The features of (34 Note that the construction of V is analogous to that of Dasgupta et al. (2011).”
Practical and Optimal LSH for Angular Distance (2015, methodology): “This is similar to pseudo-random rotations used in the context of LSH [21], dimensionality reduction [17], or compressed sensing [22].”
Learning to Hash for Indexing Big Data—A Survey (2015, methodology): “By converting rank lists to a triplet tensor matrix, listwise hashing is designed to preserve the ranking in the Hamming space [76].”
Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search (2014, methodology): “The total running cost of LSH algorithm is dominated by the query processing cost (Indyk & Motwani, 1998; Dasgupta et al., 2011).”
Circulant Binary Embedding (2014, methodology): “SupposeHk(x1,x2) is the normalized Hamming distance betweenk-bit codes of a pair of points x1,x2 ∈ Rd: Hk(x1,x2)= 1 k k−1 ∑ i=0 ∣ ∣sign(Ri·x1)−sign(Ri·x2) ∣ ∣/2, (11) andRi· is thei-th row ofR, R = circ(r).”
A Survey on Learning to Hash (2016, background): “Following the pioneering works [14], [44], there are a lot of efforts, such as proposing random hash functions satisfying the locality sensitivity property for various distance measures [10], [11], [14], [19], [20], [100], [111], proving better search efficiency and accuracy [19], [113], developing ”
An Exploration of Parameter Redundancy in Deep Networks with Circulant Projections (2015, methodology): “One could in principle use other structured matrices such as Hadamard matrices along with a sparse random Gaussian matrix to achieve fast projection as was done in the fast Johnson-Lindenstrauss transform [1, 4], but they are slower than the circulant projection and need more space.”
One Permutation Hashing (2012, methodology): “The total running cost of LSH algorithm is dominated by the query processing cost (Indyk & Motwani, 1998; Dasgupta et al., 2011).”
Hashing for Similarity Search: A Survey (2014, methodology): “Fast LSH [19] presents two algorithms, ACHash and DHHash, that formulate L K-bits compound hash functions.”