Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O'DonnellYi WuYuan ZhouPublished in: CoRR (2009)
Keyphrases
- locality sensitive hashing
- lower bound
- optimal solution
- similarity search
- nearest neighbor search
- nearest neighbor
- dynamic programming
- knn
- metric space
- hash functions
- brute force
- objective function
- space efficient
- dimensionality reduction
- distance measure
- database
- pattern matching
- sliding window
- exhaustive search
- hamming distance
- decision trees