Fast and space efficient data structure for nearest neighbors in 3 dimensions?
I like Drost's hierarchical voxel hashing. It has an average time complexity of $O(log(log(|D|)))$, where $|D|$ is the number of points in data cloud. While the construction is a bit more tedious, searching gets much faster. 

The method is also extended to a journal version, found under this link.