Efficient Approximate Nearest Neighbor Search For Multiple Weighted \(l_{p\leq2}\) Distance Functions
2020 · Huan Hu, Jianzhong Li
Abstract
Nearest neighbor search is fundamental to a wide range of applications. Since the exact nearest neighbor search suffers from the "curse of dimensionality", approximate approaches, such as Locality-Sensitive Hashing (LSH), are widely used to trade a little query accuracy for a much higher query efficiency. In many scenarios, it is necessary to perform nearest neighbor search under multiple weighted distance functions in high-dimensional spaces. This paper considers the important problem of supporting efficient approximate nearest neighbor search for multiple weighted distance functions in high-dimensional spaces. To the best of our knowledge, prior work can only solve the problem for the \(l_2\) distance. However, numerous studies have shown that the \(l_p\) distance with \(p\in(0,2)\) could be more effective than the \(l_2\) distance in high-dimensional spaces. We propose a novel method, WLSH, to address the problem for the \(l_p\) distance for \(p\in(0,2]\). WLSH takes the LSH approac
Authors
(none)
Tags
Stats
Related papers
- Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
- Sublinear Time Nearest Neighbor Search Over Generalized Weighted Manhattan Distance (2021)0.00
- Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
- PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search (2021)8.09
- Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
- Locality-sensitive Hashing For F-divergences: Mutual Information Loss And Beyond (2019)0.00
- DET-LSH: A Locality-sensitive Hashing Scheme With Dynamic Encoding Tree For Approximate Nearest Neighbor Search (2024)9.92
- Hybrid LSH: Faster Near Neighbors Reporting In High-dimensional Space (2016)0.00