pyramid match kernel image similarity code implementation, performance and accuracy issues

I am trying to utilize PMK to classify a set of images into different classes based on similarities. This is an update from my past post here: http://metaoptimize.com/qa/questions/10557/pyramid-matching-kernel-in-determining-similarity-between-images

I have implemented PMK as Andreas has described in matlab, but my results have been far from desirable. Many images that are not similar at all are mistakenly described as similar. What is the expected performance of the kernel? I would expect that something that I'm doing is not correct in my implementation.

my not so efficient code is here: http://pastebin.com/0JDs0wvz

I use vl_dsift for my features and kdtrees, am I doing something wrong here?

should I try going for scSPM? http://www.ifp.illinois.edu/~jyang29/ScSPM.htm it claims to have better performance