Query Difficulty Estimation for Image Search With Query Reconstruction Error

Current image search engines suffer from a radical variance in retrieval performance over different queries. It is therefore desirable to identify those "difficult" queries in order to handle them properly. Query difficulty estimation is an attempt to predict the performance of the search results returned by an image search system. Most existing methods for query difficulty estimation focus on investigating statistical characteristics of the returned images only, while neglecting very important information, i.e., the query and its relationship with returned images. This relationship plays a crucial role in query difficulty estimation and should be explored further. In this paper we propose a novel query difficulty estimation method with query reconstruction error. This method is proposed based on the observation that, given the images returned for an unknown query, we can easily deduce what the query is from those images if the search results are high quality (i.e., lots of relevant images returned); otherwise, it is difficult to deduce the original query. Therefore, we propose to predict the query difficulty by measuring to what extent the original query can be recovered from the image search results. Specifically, we first reconstruct a visual query from the returned images to summarize their visual theme, and then use the reconstruction error, i.e., the distance between the original textual query and the reconstructed visual query, to estimate the query difficulty. We conduct extensive experiments on two real-world Web image datasets and demonstrate the effectiveness of the proposed method.