Optimal lower bounds for locality sensitive hashing (except when q is tiny).

Ryan O'Donnell Yi Wu Yuan Zhou

Published in: Electron. Colloquium Comput. Complex. (2009)

Keyphrases

locality sensitive hashing
lower bound
similarity search
optimal solution
nearest neighbor
objective function
brute force
nearest neighbor search
indexing techniques
dynamic programming
hash functions
metric space
neural network
training data
hamming distance
space efficient