Parameter-free Locality Sensitive Hashing For Spherical Range Reporting

Abstract

We present a data structure for *spherical range reporting* on a point set \(S\), i.e., reporting all points in \(S\) that lie within radius \(r\) of a given query point \(q\). Our solution builds upon the Locality-Sensitive Hashing (LSH) framework of Indyk and Motwani, which represents the asymptotically best solutions to near neighbor problems in high dimensions. While traditional LSH data structures have several parameters whose optimal values depend on the distance distribution from \(q\) to the points of \(S\), our data structure is parameter-free, except for the space usage, which is configurable by the user. Nevertheless, its expected query time basically matches that of an LSH data structure whose parameters have been *optimally chosen for the data and query* in question under the given space constraints. In particular, our data structure provides a smooth trade-off between hard queries (typically addressed by standard LSH) and easy queries such as those where the number of poi

Stats

• citations15
• S2 citations—
• github stars0
• HF likes0
• heat score9.03
• arxiv keyahle2016parameter

Related papers

• Hybrid LSH: Faster Near Neighbors Reporting In High-dimensional Space (2016)0.00
• Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00
• Locality Sensitive Hashing For Set-queries, Motivated By Group Recommendations (2020)0.00
• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Optimal Las Vegas Locality Sensitive Data Structures (2017)6.77
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Distance-sensitive Hashing (2017)8.82