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

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), compu...

Full description

Saved in:
Bibliographic Details
Published in:PloS one 2018-01, Vol.13 (1), p.e0191175-e0191175
Main Authors: Cormode, Graham, Dasgupta, Anirban, Goyal, Amit, Lee, Chi Hoon
Format: Article
Language:English
Subjects:
Algorithms
Artificial intelligence
Biology and Life Sciences
Browsing
Cloud computing
Computation
Computer and Information Sciences
Computer applications
Computer networks
Computer science
Data analysis
Distributed processing
Engineering and Technology
Engineering research
Hashing (Computer programming)
Image processing
Innovations
International conferences
Knowledge management
Language
Linguistics
Methods
Natural language processing
Optimization theory
Physical Sciences
Queries
Research and Analysis Methods
Search engines
Very large scale
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1932-6203
1932-6203
DOI:10.1371/journal.pone.0191175