The cool thing about VP trees is that your space doesn't have to be Euclidean, i.e. you can have dimensions that depend on other dimensions, e.g. in RGBA color space values of RGB are meaningless when A=transparent. You can't search that space with KD trees, but you can with VP trees.