In the previous post, we discussed that LSH addresses the \(c\)-NNS problem by solving multiple \((R,c)\)-NNS problems using different radii. In this article, we will explore how to construct LSH families specifically designed to solve the \((R,c)\)-NNS problems under the \(\ell_p\) norm, leveraging the properties of \(p\)-stable distribution.

This article introduces Locality-Sensitive Hashing (LSH) as an effective technique for Approximate Nearest Neighbor Search (ANNS) in high-dimensional spaces, addressing the “curse of dimensionality.” By using hash functions that map similar data points into the same buckets, LSH reduces the general \(c\)-NNS problem into manageable \((R, c)\)-NNS subproblems. This approach enables fast approximate searches with acceptable accuracy, effectively tackling the challenges of high-dimensional data search.