Skip to main content

Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond

Author(s): Lv, Qin; Josephson, William; Wang, Zhe; Charikar, Moses; Li, Kai

To refer to this page use:
Abstract: The past decade has been marked by the (continued) explosion of diverse data content and the fast development of intelligent data analytics techniques. One problem we identified in the mid-2000s was similarity search of feature-rich data. The challenge here was achieving both high accuracy and high efficiency in high-dimensional spaces. Locality sensitive hashing (LSH), which uses certain random space partitions and hash table lookups to find approximate nearest neighbors, was a promising approach with theoretical guarantees. But LSH alone was insufficient since a large number of hash tables were required to achieve good search quality. Building on an idea of Panigrahy, our multi-probe LSH method introduced the idea of intelligent probing. Given a query object, we strategically probe its neighboring hash buckets (in a query-dependent fashion) by calculating the statistical probabilities of similar objects falling into each bucket. Such intelligent probing can significantly reduce the number of hash tables while achieving high quality. In this paper, we revisit the problem motivation, the challenges, the key design considerations of multi-probe LSH, as well as discuss recent developments in this space and some questions for further research.
Publication Date: Aug-2017
Citation: Lv, Qin, William Josephson, Zhe Wang, Moses Charikar, and Kai Li. "Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond." Proceedings of the VLDB Endowment 10, no. 12 (2017): pp. 2021-2024. doi:10.14778/3137765.3137836
DOI: 10.14778/3137765.3137836
ISSN: 2150-8097
Pages: 2021 - 2024
Type of Material: Conference Article
Journal/Proceeding Title: Proceedings of the VLDB Endowment
Version: Final published version. Article is made available in OAR by the publisher's permission or policy.

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.