Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing.
Alexandr AndoniIlya P. RazenshteynPublished in: CoRR (2015)
Keyphrases
- data dependent
- lower bound
- locality sensitive hashing
- hash functions
- upper bound
- similarity search
- nearest neighbor
- nearest neighbor search
- brute force
- worst case
- optimal solution
- hamming distance
- objective function
- indexing techniques
- knn
- multimedia retrieval
- space efficient
- sift features
- metric space
- data distribution
- neural network
- range queries
- distance function