Probabilistic feature relevance learning (PFRL) is an effective technique for adaptively computing local feature relevance for content-based image retrieval. It however becomes less attractive in situations where all the input variables have the same local relevance, and yet retrieval performance might still be improved by simple query shifting. We propose a retrieval method that combines feature relevance learning and query shifting to try to achieve the best of both worlds. We use a linear discriminant analysis to compute the new query and exploit the local neighborhood structure centered at the new query by invoking PFRL. As a result, the modified neighborhoods at the new query tend to contain sample images that are more relevant to the input query. The efficacy of our method is validated using both synthetic and real world data.