Use KDTrees to support nearest neighbor queries/joins on MultiIndexes?
If we're willing to construct KDTrees when necessary, we can support efficient nearest neighbor queries even in multiple dimensions (i.e., on a MultiIndex) and even for unsorted indexes. 

For an example of what you can do with this, take a look at this question I just answered on SO: http://stackoverflow.com/a/28186940/809705

See also: 1d nearest neighbor queries (#8845) and an implementation for sorted indexes (#9258).
