Abstract: We present a data clustering method for robust SIFT matching. Our matching process contains an offline module to cluster features from a group of reference images and an online module to match them to the live images in order to enhance matching robustness. The main contribution lies in constructing a composite k-d data structure which can be used not only to cluster features but also to implement features matching. Then an optimal keyframe selection method is proposed using our composite k-d tree, which can not only put the matching process forward but also give us a way to employ a cascading feature matching strategy to combine matching results of composite k-d tree and keyframe. Experimental results show that our method dramatically enhances matching robustness.