An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.
Amit ChakrabartiOded RegevPublished in: FOCS (2004)
Keyphrases
- nearest neighbour
- lower bound
- optimal solution
- worst case
- upper bound
- provide an upper bound
- optimal cost
- k nearest neighbour
- branch and bound algorithm
- objective function
- competitive ratio
- euclidean distance
- k nearest neighbor
- lower and upper bounds
- knn
- branch and bound
- dynamic programming
- constant factor
- similarity search
- data sets
- information extraction
- search procedure
- optimal strategy
- feature vectors
- expert systems
- pattern recognition
- image processing