This is a very important data structure from a historical point of view, but unfortunately it doesn't work well when you are dealing with complex spaces. Try LSH as mentioned before or something that is 10X faster: http://simmachines.com

Don't waste your time on space partitioning trees if you have big data, jump straight to Locality Sensitive Hashing or approximate nearest neighbor graph construction (WWW 2011)

I'm no expert, but this doesn't seem to be any significantly better than a k-d tree, does it? I might be missing something. I find academic papers hard to parse.