2017/08/24 by Tobias Christiani, Christiani, Tobias
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #E.1 #FOS: Computer and information sciences #H.3.3 #Multimodal Machine Learning Applications
paper · pdf · doi:10.48550/arxiv.1708.07586
openalex publication_date 2017/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Indyk-Motwani Locality-Sensitive Hashing (LSH) framework (STOC 1998) is a\ngeneral technique for constructing a data structure to answer approximate near\nneighbor queries by using a distribution \H over locality-sensitive\nhash functions that partition space. For a collection of n points, after\npreprocessing, the query time is dominated by O(n\ρ \log n) evaluations\nof hash functions from \H and O(n\ρ) hash table lookups and\ndistance computations where \ρ \∈ (0,1) is determined by the\nlocality-sensitivity properties of \H. It follows from a recent\nresult by Dahlgaard et al. (FOCS 2017) that the number of locality-sensitive\nhash functions can be reduced to O(\log2 n), leaving the query time to be\ndominated by O(n\ρ) distance computations and O(n\ρ \log n)\nadditional word-RAM operations. We state this result as a general framework and\nprovide a simpler analysis showing that the number of lookups and distance\ncomputations closely match the Indyk-Motwani framework, making it a viable\nreplacement in practice. Using ideas from another locality-sensitive hashing\nframework by Andoni and Indyk (SODA 2006) we are able to reduce the number of\nadditional word-RAM operations to O(n^\ρ).\n