An evaluation of multi-probe locality sensitive hashing for computing similarities over web-scale query logs

Journal article

Many modern applications of AI such as web search, mobile browsing, image processing, and natural language processing rely on finding similar items from a large database of complex objects. Due to the very large scale of data involved (e.g., users’ queries from commercial search engines), computing such near or nearest neighbors is a non-trivial task, as the computational cost grows significantly with the number of items. To address this challenge, we adopt Locality Sensitive Hashing (a.k.a, LSH) methods and evaluate four variants in a distributed computing environment (specifically, Hadoop). We identify several optimizations which improve performance, suitable for deployment in very large scale settings. The experimental results demonstrate our variants of LSH achieve the robust performance with better recall compared with “vanilla” LSH, even when using the same amount of space.Graham Cormode;Anirban Dasgupta;Amit Goyal;Chi Hoon Le

Authors: Cormode, G; Dasgupta, A; Goyal, A; Lee, CH

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Public Library of Science
• Journal: PLoS ONE
• Volume: 13
• Issue: 1
• Pages: e0191175-e0191175
• Publication date: 2018-01-18
• DOI: 10.1371/journal.pone.0191175
• EISSN: 1932-6203
• ISSN: 1932-6203
• Language: English
• Keywords: Task (project management); Web search query; Information retrieval; Data mining; Hash table; Locality-sensitive hashing; Locality; Search engine; Scale (ratio); Software deployment; Hash function; Computer science