You can solve complex things with k-nearest neighbor as long as you use an appropriate distance function. This is the beauty, a distance function abstracts the complexity. I tackled a tricky biology problem by applying a cascade of similarity filters. Check the presentation I gave at the Clojure/conj 2011: http://prezi.com/zaaoq6pjrl2z/clojure-conj-final/

My startup provides a very fast similarity engine (in a DB of 100 million objects I can find similar objects in under 20 millisec. with one CPU) in case you worry about scalability. URL: http://simmachines.com