2011 FastLocalitySensitiveHashing

• (Dasgupta et al., 2011) ⇒ Anirban Dasgupta, Ravi Kumar, and Tamas Sarlos. (2011). “Fast Locality-sensitive Hashing.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020578

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Fast+Locality-sensitive+Hashing
• http://dl.acm.org/citation.cfm?id=2020408.2020578&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; dimension reduction; hadamard transform; information search and retrieval; locality sensitive hashing; nearest neighbour search

Abstract

Locality-sensitive hashing (LSH) is a basic primitive in several large-scale data processing applications, including nearest-neighbor search, de-duplication, clustering, etc. In this paper we propose a new and simple method to speed up the widely-used Euclidean realization of LSH. At the heart of our method is a fast way to estimate the Euclidean distance between two d-dimensional vectors; this is achieved by the use of randomized Hadamard transforms in a non-linear setting. This decreases the running time of a k, L -parameterized LSH from [math]\displaystyle{ O (dkL) }[/math]to [math]\displaystyle{ O(d\log\;d + kL) }[/math]. Our experiments show that using the new LSH in nearest-neighbor applications can improve their running times by significant amounts. To the best of our knowledge, this is the first running time improvement to LSH that is both provable and practical.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 FastLocalitySensitiveHashing	Ravi Kumar Anirban Dasgupta Tamas Sarlos			Fast Locality-sensitive Hashing				10.1145/2020408.2020578		2011