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

Ryan O'Donnell Yi Wu Yuan Zhou

Published in: ICS (2011)

Keyphrases

locality sensitive hashing
lower bound
optimal solution
nearest neighbor
similarity search
hash functions
dynamic programming
brute force
multiscale
objective function
range query processing
data structure
nearest neighbor search
sift features