Cannot find paper: All k nearest neighbors search in N*log(N) using distance indices for log(N) support points
Found the paper finally. Not sure I've read exactly the same paper (maybe I read some SO or SE answer or some other paper that inspired/was inspired by this paper). Nethertheless, the algorithm is exactly the same.

A Fast Algorithm for the All k Nearest Neighbors Problem in General Metric Spaces by Edgar Chávez and Karina Figueroa and Gonzalo Navarro. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.21.9299 http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=A580FE7BF3251BC23DB793E3B1DFDF64?doi=10.1.1.21.9299&amp;rep=rep1&amp;type=pdf