General question about nearest neighbor

I want to improve the speed of my feature matching algorithm. The matching is based on comparing feature A with circularly shifted feature B. The shifting is performed N times (for orientation invariance). The distance between A and B is the minimal value of the distance between A and the shifted B.

Considering this distance, I cannot use a KD tree or the FLANN library.

What kind of solutions could be applied in my case in order to speed up the NN search? Is there any c++ library that I can use?