Hardness of Nearest Neighbor under L-infinity.
Alexandr AndoniDorian CroitoruMihai PatrascuPublished in: FOCS (2008)
Keyphrases
- nearest neighbor
- k nearest neighbor
- knn
- distance function
- training set
- high dimensional
- high dimensional data
- phase transition
- nearest neighbor search
- np hard
- np complete
- computational complexity
- worst case
- reverse nearest neighbor
- data sets
- nearest neighbor classifier
- data points
- index structure
- case study
- learning theory
- locality sensitive hashing
- information retrieval
- nearest neighbor algorithm
- similarity measure
- artificial intelligence
- databases