An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching
Amit ChakrabartiOded RegevPublished in: Electron. Colloquium Comput. Complex. (2003)
Keyphrases
- nearest neighbour
- lower bound
- optimal solution
- worst case
- upper bound
- provide an upper bound
- piecewise linear
- branch and bound algorithm
- competitive ratio
- dynamic programming
- optimal cost
- objective function
- lower and upper bounds
- k nearest neighbour
- training set
- np hard
- knn
- decision trees
- constant factor
- neural network
- regret bounds
- data mining
- artificial intelligence
- expert systems