2015 SelectiveHashingClosingtheGapBe

• (Gao et al., 2015) ⇒ Jinyang Gao, H.V. Jagadish, Beng Chin Ooi, and Sheng Wang. (2015). “Selective Hashing: Closing the Gap Between Radius Search and K-NN Search.” In: Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2015). ISBN:978-1-4503-3664-2 doi:10.1145/2783258.2783284

Subject Headings: Locality-Sensitive Hashing.

Cited By

• http://scholar.google.com/scholar?q=%222015%22+Selective+Hashing%3A+Closing+the+Gap+Between+Radius+Search+and+K-NN+Search
• http://dl.acm.org/citation.cfm?id=2783258.2783284&preflayout=flat#citedby

Quotes

Author Keywords

• Adaptive hashing; composite structures; data sensitive hashing; hash-table representations; high-dimensional indexing; locality sensitive hashing; lsh; selective hashing

Abstract

Locality Sensitive Hashing (LSH) and its variants, are generally believed to be the most effective radius search methods in high-dimensional spaces. However, many applications involve finding the k nearest neighbors (k-NN), where the k-NN distances of different query points may differ greatly and the performance of LSH suffers. We propose a novel indexing scheme called Selective Hashing, where a disjoint set of indices are built with different granularities and each point is only stored in the most effective index. Theoretically, we show that k-NN search using selective hashing can achieve the same recall as a fixed radius LSH search, using a radius equal to the distance of the c ₁ k _th nearest neighbor, with at most c ₂ times overhead, where c ₁ and c ₂ are small constants. Selective hashing is also easy to build and update, and outperforms all the state-of-the-art algorithms such as DSH and IsoHash.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2015 SelectiveHashingClosingtheGapBe	Jinyang Gao H.V. Jagadish Beng Chin Ooi Sheng Wang			Selective Hashing: Closing the Gap Between Radius Search and K-NN Search				10.1145/2783258.2783284		2015