Nearest Neighbor Search: the Old, the New, and the Impossible, the MIT PhD thesis of Alexandr Andoni.
To be honest, it is the discovery of gems like this one that keep me prowling journals, pre-publication sites, homepages, etc.
Alexandr walks the reader through a very complete review of the literature on nearest neighbor search, all the while laying a foundation for the significant progress he has made.
Not for the faint of heart but it promises to be well worth the effort.