Luckily, there are solutions for every problem above – for example, the Locality Sensitive Hashing for solving the expensive computation cost, Distance metric learning for approximating the ‘correct’ distance metric, and Random projection, as well as other dimension reduction techniques, for the breaking the curse of dimensionality. These topics will be further exploit, in future blog posts.
 Cover and Hart (1967), Nearest neighbor pattern recognition, IEEE Transactions on Information Theory 13; p.21-27
 Beyer, K.; Goldstein, J.; Ramakrishnan, R.; Shaft, U. (1999), When is “Nearest Neighbor” Meaningful?, Proc. 7th International Conference on Database Theory – ICDT’99. LNCS. 1540: 217235
 Yang and Liu (2006), Distance Metric Learning: A Comprehensive Survey.
 Dimitris Achlioptas (2003), Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journay of Computer and System Sciences, 66(4):671687.