Hybrid LSH: Faster Near Neighbors Reporting In High-dimensional Space

Abstract

We study the \(r\)-near neighbors reporting problem (\(r\)-NN), i.e., reporting *all* points in a high-dimensional point set \(S\) that lie within a radius \(r\) of a given query point \(q\). Our approach builds upon on the locality-sensitive hashing (LSH) framework due to its appealing asymptotic sublinear query time for near neighbor search problems in high-dimensional space. A bottleneck of the traditional LSH scheme for solving \(r\)-NN is that its performance is sensitive to data and query-dependent parameters. On datasets whose data distributions have diverse local density patterns, LSH with inappropriate tuning parameters can sometimes be outperformed by a simple linear search. In this paper, we introduce a hybrid search strategy between LSH-based search and linear search for \(r\)-NN in high-dimensional space. By integrating an auxiliary data structure into LSH hash tables, we can efficiently estimate the computational cost of LSH-based search for a given query regardless of

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keypham2016hybrid

Related papers

• Parameter-free Locality Sensitive Hashing For Spherical Range Reporting (2016)9.03
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00
• PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
• Fair Near Neighbor Search: Independent Range Sampling In High Dimensions (2019)8.82
• Locality Sensitive Hashing For Set-queries, Motivated By Group Recommendations (2020)0.00