Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny).

Ryan O'Donnell Yi Wu Yuan Zhou

Published in: ACM Trans. Comput. Theory (2014)

Keyphrases

locality sensitive hashing
lower bound
brute force
nearest neighbor
optimal solution
similarity search
nearest neighbor search
dynamic programming
hash functions
objective function
exhaustive search
database
multiscale
hamming distance