nearest neighbor

an introduction to Nearest Neighbor
http://people.csail.mit.edu/gregory/annbook/introduction.pdf

• other names: best match
• method:
  
  • Nearest neighbor(exact);
  • Approximate nearest neighbor (ANN) - more efficent;
    
    • kdtree: construct time: O(n log n); modified: BBF(piority)
    • Balltrees and Metric Trees;
    • exhausive,
    • LSH = Randomized c-approximate near-neighbor
    • HK-means
  • application: image completetion;