PM-LSH: A Fast And Accurate In-memory Framework For High-dimensional Approximate NN And Closest Pair Search
2021 · Bolong Zheng, Xi Zhao, Lianggui Weng, et al.
Abstract
Nearest neighbor (NN) search is inherently computationally expensive in high-dimensional spaces due to the curse of dimensionality. As a well-known solution, locality-sensitive hashing (LSH) is able to answer c-approximate NN (c-ANN) queries in sublinear time with constant probability. Existing LSH methods focus mainly on building hash bucket-based indexing such that the candidate points can be retrieved quickly. However, existing coarse-grained structures fail to offer accurate distance estimation for candidate points, which translates into additional computational overhead when having to examine unnecessary points. This in turn reduces the performance of query processing. In contrast, we propose a fast and accurate in-memory LSH framework, called PM-LSH, that aims to compute c-ANN queries on large-scale, high-dimensional datasets. First, we adopt a simple yet effective PM-tree to index the data points. Second, we develop a tunable confidence interval to achieve accurate distance esti
Authors
(none)
Tags
Stats
Related papers
- Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
- DET-LSH: A Locality-sensitive Hashing Scheme With Dynamic Encoding Tree For Approximate Nearest Neighbor Search (2024)9.92
- Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
- Lorann: Low-rank Matrix Factorization For Approximate Nearest Neighbor Search (2024)2.26
- Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors (2017)0.00
- MP-RW-LSH: An Efficient Multi-probe LSH Solution To ANNS In \(L_1\) Distance (2021)0.00
- Hybrid LSH: Faster Near Neighbors Reporting In High-dimensional Space (2016)0.00
- Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81