MP-RW-LSH: An Efficient Multi-probe LSH Solution To ANNS In \(L_1\) Distance

Abstract

Approximate Nearest Neighbor Search (ANNS) is a fundamental algorithmic problem, with numerous applications in many areas of computer science. Locality-sensitive hashing (LSH) is one of the most popular solution approaches for ANNS. A common shortcoming of many LSH schemes is that since they probe only a single bucket in a hash table, they need to use a large number of hash tables to achieve a high query accuracy. For ANNS-\(L_2\), a multi-probe scheme was proposed to overcome this drawback by strategically probing multiple buckets in a hash table. In this work, we propose MP-RW-LSH, the first and so far only multi-probe LSH solution to ANNS in \(L_1\) distance. Another contribution of this work is to explain why a state-of-the-art ANNS-\(L_1\) solution called Cauchy projection LSH (CP-LSH) is fundamentally not suitable for multi-probe extension. We show that MP-RW-LSH uses 15 to 53 times fewer hash tables than CP-LSH for achieving similar query accuracies.

Stats

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

Related papers

• 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
• 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
• Improving Locality Sensitive Hashing By Efficiently Finding Projected Nearest Neighbors (2020)6.77
• Experimental Analysis Of Locality Sensitive Hashing Techniques For High-dimensional Approximate Nearest Neighbor Searches (2020)6.34
• Fast Locality-sensitive Hashing Frameworks For Approximate Near Neighbor Search (2017)7.81
• A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19