Data structure for Nearest Neighbor Search - VP Trees(pnylab.com)
pnylab.com
Data structure for Nearest Neighbor Search - VP Trees
http://pnylab.com/pny/papers/vptree/vptree/
3 comments
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
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.
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)