Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing.
Alexandr AndoniIlya P. RazenshteynPublished in: SoCG (2016)
Keyphrases
- data dependent
- lower bound
- locality sensitive hashing
- hash functions
- upper bound
- similarity search
- nearest neighbor search
- brute force
- nearest neighbor
- objective function
- worst case
- hamming distance
- indexing techniques
- sift features
- metric space
- exhaustive search
- multimedia retrieval
- range queries
- space efficient
- knn
- optimal solution
- machine learning
- range query processing
- data distribution
- euclidean distance
- decision trees
- image processing