Multi-level Spherical Locality Sensitive Hashing For Approximate Near Neighbors

Brooks Teresa Nicole, Almajalid Rania. Arxiv 2017

[Paper]    
ARXIV Independent LSH

This paper introduces “Multi-Level Spherical LSH”: parameter-free, a multi-level, data-dependant Locality Sensitive Hashing data structure for solving the Approximate Near Neighbors Problem (ANN). This data structure uses a modified version of a multi-probe adaptive querying algorithm, with the potential of achieving a $O(n^p+t)$ query run time, for all inputs n where $t<=n$.

Similar Work

• Parameter-free Locality Sensitive Hashing For Spherical Range Reporting
• Optimal Data-dependent Hashing For Approximate Near Neighbors
• Fast Approximate Nearest-neighbor Field By Cascaded Spherical Hashing
• Practical And Optimal LSH For Angular Distance